Jump to content

Talk:Heilbronn triangle problem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Comments

[edit]
If we are posing the question of the worst case for the existence of small triangles, it will happen with all the chosen points on the boundary.

Might be true (in some sense, asymptotically) but I no longer find this at all evident. Another way to pose the question: for P, Q points from the configuration X, the line segment PG having length L, we want to draw strips of width inversely proportional to L and look whether any other point R lies in them (because the area of the triangle PQR is L times the perpendicular distance from R to the line).

Charles Matthews 09:35, 25 Sep 2004 (UTC)

Your GA nomination of Heilbronn triangle problem

[edit]

Hi there, I'm pleased to inform you that I've begun reviewing the article "Heilbronn triangle problem" you nominated for GA-status according to the criteria. This process may take up to 7 days. Feel free to contact me with any questions or comments you might have during this period. Eluike (talk) 19:43, 8 April 2022 (UTC)[reply]

Note: reviewer was blocked indefinitely; review has been deleted and nomination returned to pool of those awaiting a review with no loss of seniority. BlueMoonset (talk) 05:13, 9 April 2022 (UTC)[reply]

GA Review

[edit]
GA toolbox
Reviewing
This review is transcluded from Talk:Heilbronn triangle problem/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Ovinus (talk · contribs) 14:55, 19 April 2022 (UTC)[reply]

I'll take another one. Ovinus (talk) 14:55, 19 April 2022 (UTC)[reply]

Initial comments

[edit]

Looks good overall. Understandable for most undergraduate CS students, I'd say. Ovinus (talk) 14:55, 19 April 2022 (UTC)[reply]

All looks good; I made one clarifying comment above. I'll pass in a bit. Ovinus (talk) 19:08, 20 April 2022 (UTC)[reply]

Some specimen solutions

[edit]

Some readers might find the article more appealing if it included "eye candy" in the form of some optimal solutions for n around 10. There's plenty of material at https://mathworld.wolfram.com/HeilbronnTriangleProblem.html. The images there are copyright, but I don't believe the coordinates are, so making SVGs should not be hard. Maproom (talk) 07:36, 20 April 2022 (UTC)[reply]

That page does not seem to provide formulas for the coordinates. Do you know a source for them? —David Eppstein (talk) 07:58, 20 April 2022 (UTC)[reply]
[1] cites "F. Comellas and J. Yebra. New lower bounds for Heilbronn numbers. Electronic J. of Combinatorics" (2003) as having the best known solutions for 7–10 of that time. I don't have access to it, but maybe one of you does. Ovinus (talk) 13:45, 20 April 2022 (UTC)[reply]
Actually, never mind, it's open access. They're on page 5. Ovinus (talk) 13:48, 20 April 2022 (UTC)[reply]
Thanks for finding those! That'll save some work. I'll get around to it some time – maybe a month. It's fascinating that the six examples you link to, 7..12 points in a square, all have different symmetries. Maproom (talk) 15:57, 21 April 2022 (UTC)[reply]
I've started. And I've found that the − signs in that source aren't really - signs, they're − characters that generate error messages when used in math expressions. Maproom (talk) 14:37, 27 April 2022 (UTC)[reply]
Haha. Apparently there's at least four minus signs. I guess LaTeX outputs U+2212 MINUS instead of hyphen minus, which makes sense. Ovinus (talk) 22:39, 28 April 2022 (UTC)[reply]
I've uploaded them to Commons and added them to the article. If you want to move them, change the captions, etc., please go ahead. Maproom (talk) 14:55, 4 May 2022 (UTC)[reply]
Could you please make an effort to include some explanatory text and to follow the same citation style as the rest of the article? (List-defined references, Citation Style 2 not Citation Style 1.) —David Eppstein (talk) 15:06, 4 May 2022 (UTC)[reply]
They look pretty nice, but a little busy. I'd make the lines gray so that the points are emphasized, and if possible, highlight a single one of the minimal area triangles. Ovinus (talk) 01:14, 5 May 2022 (UTC)[reply]
Anyway, I reformatted them and added a three-digit approximation to the minimum areas of each. The term "specimen" is a little funky, since it implies that they are just examples of solutions, when in fact they are the best known, so I adjusted that (but wouldn't be opposed to the original heading). Ovinus (talk) 01:45, 5 May 2022 (UTC)[reply]
Thank you, David Eppstein and Ovinus, for your suggestions, and for implementing most of them.
As for "a little busy", I've replaced the black lines by grey lines, for just the first of the images for now. Do you think the lines are now too light, or still too dark, or just right? It's very easy for me to rebuild the images. Uploading them all will be rather more hassle.
As for "highlight a single one of the minimal triangles", there are two issues.
  1. Which triangle? I could choose one by eyeballing them, which would be (A) original research, and (B) possibly wrong. Or I could push their coordinates through some area-calculating code, which would be (A) original research, and (B) more work than I'm keen to do, and might still be wrong. Less likely wrong, but I do make mistakes.
  2. These are diagrams where the minimal areas have been maximised, so there won't be a unique minimal triangle. There will in general be two non-congruent triangles with the minimal area. Highlighting just one seems to me misleading. Highlighting two adds weight to issues (A) and (B) above.
Anyway, the data are below, in the unlikely event that someone else fancies using them. Maproom (talk) 20:30, 5 May 2022 (UTC)[reply]
boring data

$n = 7; 

 my $z = 0.287258; 
 $p[0] = [ -$z*50/19-$z*$z*17/38 +37/38,  0               ];
 $p[1] = [ 1,                             0               ];
 $p[2] = [ 0,                             $z              ];
 $p[3] = [ 9/19+$z*$z/19+$z*7/19,         $z              ];
 $p[4] = [ $z*$z*40/19 +$z*223/19-58/19,  -1 +6*$z +$z*$z ];
 $p[5] = [ $z*58/19-15/19 +$z*$z*11/19,   1               ];
 $p[6] = [ 1,                             1               ];

$n = 8; 

 my $p = sqrt(13); 
 $p[0] = [ 0,          0               ];
 $p[1] = [ (1+$p)/6,   0               ];
 $p[2] = [ 1,          (7-$p)/18       ];
 $p[3] = [ (5-$p)/6,   (7-$p)/9        ];
 $p[4] = [ (1+$p)/6,    (2+$p)/9       ];
 $p[5] = [ 0,          (11+$p)/18      ];
 $p[6] = [ (5-$p)/6,   1               ];
 $p[7] = [ 1,          1               ];

$n = 9; 

 $p = sqrt(65); 
 $p[0] = [ (10-$p)/10,   0            ];
 $p[1] = [ (25+$p)/40,   0            ];
 $p[2] = [ 0,            (15-$p)/40   ];
 $p[3] = [ 1,            (15-$p)/40   ];
 $p[4] = [ (15-$p)/20,   (5+$p)/20    ];
 $p[5] = [ 0,            (35+3*$p)/80 ];
 $p[6] = [ 1,            $p/10        ];
 $p[7] = [ (45-3*$p)/80, 1            ];
 $p[8] = [ (25+$p)/40,   1            ];

$n = 10; 

 my $x = 0.157806;
 my $y = 0.252387;
 $z = 0.315611;
 $p[0] = [ $x,   0    ];
 $p[1] = [ 1-$y, 0    ];
 $p[2] = [ 0,    $x   ];
 $p[3] = [ 1,    $y   ];
 $p[4] = [ 1-$z, $z   ];
 $p[5] = [ $z,   1-$z ];
 $p[6] = [ 0,    1-$y ];
 $p[7] = [ 1,    1-$x ];
 $p[8] = [ $y,   1    ];
 $p[9] = [ 1-$x, 1    ];

$n = 11; 

 $p[0] = [ 1/3, 0   ];
 $p[1] = [ 2/3, 0   ];
 $p[2] = [ 0,   2/9 ];
 $p[3] = [ 1,   2/9 ];
 $p[4] = [ 1/3, 4/9 ];
 $p[5] = [ 2/3, 4/9 ];
 $p[6] = [ 0,  2/3  ];
 $p[7] = [ 1,  2/3  ];
 $p[8] = [ 1/2, 7/9 ];
 $p[9] = [ 1/6, 1   ];
$p[10] = [ 5/6, 1   ];

$n = 12; 

 $x = 0.115354;
 $y = 0.180552;
 $p[0] = [ $x,   0    ];
 $p[1] = [ 1-$x, 0    ];
 $p[2] = [ 0,    $x   ];
 $p[3] = [ 1,    $x   ];
 $p[4] = [ 1/2,  $y   ];
 $p[5] = [ $y,   1/2  ];
 $p[6] = [ 1-$y, 1/2  ];
 $p[7] = [ 1/2,  1-$y ];
 $p[8] = [ 0,    1-$x ];
 $p[9] = [ 1,    1-$x ];
$p[10] = [ $x,   1    ];
$p[11] = [ 1-$x, 1    ];

The replacement with gray edges looks a little light to me — either the points or the lines need to be stronger, to see it more clearly. I thought the black edge versions were ok. —David Eppstein (talk) 20:33, 5 May 2022 (UTC)[reply]

I've made the first one darker again, but not black. The points are black, but could be made larger. Maproom (talk) 20:41, 5 May 2022 (UTC)[reply]
Someone who's interested in one of these diagrams will, I hope, click on it so as to view the larger version at Commons. And that's what I mostly consider when I'm deciding the line widths, colours, etc. Maproom (talk) 21:02, 5 May 2022 (UTC)[reply]
I've coloured in the minimal-area triangles for the first image. There are five of them, none congruent – this shouldn't have surprised me, considering how many degrees of freedom there are and what the solver is maximising.
If I'd made them all grey, it would be hard to make out the actual triangles, so I've used colours. I can trivially change the colours, and degree of opacity. But I don't like the result, and I don't welcome the work I'd need to do for the other diagrams. But shading an arbitrary subset of the minimal triangles feels unhelpful.
I await your comments. Maproom (talk) 20:56, 6 May 2022 (UTC)[reply]
The colored shading looks good to me. I think it makes the image significantly more informative, and it is quite legible even at thumbnail sizes. —David Eppstein (talk) 00:18, 7 May 2022 (UTC)[reply]
Ok, I'll stick with that, at least for the 7-point diagram. It currently contains a mistake, there are seven non-congruent smallest triangles, not five. I'll fix that, probably later today, and then consider colouring the other diagrams. Any suggestions for making the shading more or less prominent, the vertices bigger or smaller, etc., can be handled in a few seconds, so please offer them here. Maybe the background should be light grey not light green, freeing up a tint for the overlapping coloured triangles. Maproom (talk) 09:31, 7 May 2022 (UTC)[reply]
I've now shaded all the minimal triangles for each diagram, omitting those which are related to others by symmetry and so are congruent. At least, that's my intention. I observe that for five of the six diagrams, the number of triangles I've shaded is one more than the number of degrees of freedom in nudging the vertices around to optimise the minimum; I find this encouraging, it suggests that I've shaded the right numbers of triangles. But for the 11-point diagram, there are 7 degrees of freedom and thirteen triangles. This may indicate some error, so I'll be grateful if someone can check.
I'm not planning to make many more changes, though I'll gladly run my program to make any changes that people suggest here. One thing I might do is to adjust the crosshatching used in the 7- and 11-vertex diagrams; I think it's too heavy at present, particularly as seen in the thumbnails. I might also add some text to explain the "all non-congruent minimal triangles" business; but I can't at present find a way to word it which gets the meaning across, doesn't sound clumsy, and doesn't confuse readers who don't really care about it. Maproom (talk) 21:35, 7 May 2022 (UTC)[reply]
I've lightened the heavy hatching. Maproom (talk) 21:49, 7 May 2022 (UTC)[reply]
... and used a footnote for the "non-congruent" thing. Maproom (talk) 08:25, 8 May 2022 (UTC)[reply]
[edit]

I'm making this a new section rather than appending it to the one above. I consider most of the stuff discussed in the above section as resolved, though I'm open to suggestions for changes in the diagrams. But there's one aspect which still worries me.

When Ovinus suggested "highlight a single one of the minimal area triangles", my views followed this trajectory:

  1. There'll only be a few minimal triangles for each diagram, I'll colour them all.
  2. Oh dear, there's a lot more minimal triangles than I expected – 28 for the 11-point case. I can't highlight them them all. But most of the diagrams have some symmetry. The minimal triangles fall into sets, with with symmetries of the diagram mapping members of a set to one another. I'll just highlight one member of each such set.
  3. I can reduce the number of highlighted triangles further, because
    1. When a diagram has rotational symmetry, there are lots of parallelograms. Specifically, if it has 2-fold rotational symmetry and 2n points, there are at least n(n-1)/2 parallelograms.
    2. The vertices of a parallelogram define four triangles all of equal area.
    so there are plenty of cases where two triangles in a symmetric diagram necessarily have the same minimal area, even though there's no symmetry operation that maps one to the other. I need not highlight triangles that are "duplicates" in this way.
    The current state of the diagrams reflects is intended to reflect this logic.
  4. In the diagram for the 11-point case there are four parallelograms whose existence is not a consequence of the overall symmetry of the diagram, and which are small (thin) enough that halving them along a diagonal gives minimal triangles. Using this I could reduce the number of "independently" minimal triangles to highlight by (I think) five. This would make that diagram look less messy.

I'm not going to do anything about this for a while. Maybe my thoughts will be different in a few days. Maybe someone will offer some good advice.

I've long stopped pretending to myself that I'm avoiding WP:OR. Maybe WP:OR doesn't apply to diagrams? If I add a picture of a dandelion to Taraxacum, no-one complains about WP:OR.   Maproom (talk) 19:35, 8 May 2022 (UTC)[reply]

It's definitely possible for WP:OR to apply to diagrams. But in this case the coordinates are sourced, and the question of which triangles are smallest falls under WP:CALC. So the only OR issue is your choice of which triangles to highlight; that seems insufficiently significant to be a problem to me. —David Eppstein (talk) 20:39, 8 May 2022 (UTC)[reply]
Agreed with David that the smallest triangles, and the number of them, are roughly within WP:CALC. In any case, your choice of highlighting isn't a big deal. The footnote [d] is perhaps pushing it, but... meh, bigger fish to fry imho. Indeed, great work on these diagrams! :) For the 11 point diagram, are the horizontal-line-shaded triangle and upper vertical-line-shaded triangle not congruent? Ovinus (talk) 03:16, 9 May 2022 (UTC)[reply]
Thank you, Ovinus, for your improvement to the footnote. Yes, those two triangles are congruent. But that's so because the horizontal edge joining their non-common vertices is midway between the two horizontal edges that run from the left side of the square to the right side – it's not a consequence of the symmetry of the overall diagram (a vertical mirror). I'll probably be removing the shading from one of those two, but I want another day or two to clear my head first. Maproom (talk) 08:42, 9 May 2022 (UTC)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Heilbronn_triangle_problem&oldid=1202655783"