Talk:Heilbronn triangle problem

Comments

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

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)

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)

GA Review

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)

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

Initial comments

• "some triangle will have an" Maybe just "the smallest triangle will have an" Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • Changed to "the smallest triangle area will be" —David Eppstein (talk) 17:49, 20 April 2022 (UTC)
• "who conjectured that, no matter" How about "who made a related conjecture that", so that it's clear that his conjecture is not the problem itself Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • But it is the same problem (how big is the smallest triangle). It is just a wrong guess at what the solution to the problem would be. —David Eppstein (talk) 17:50, 20 April 2022 (UTC)
    • True. Ovinus (talk) 19:08, 20 April 2022 (UTC)
• "The assumption that the shape is compact implies that there exists a placement of $n$ points whose minimum triangle area is at least as large as for any other placement" So basically the existence of a maximum vs. only a supremum? Why not just "The assumption that the shape is compact implies that there exists an optimal placement of $n$ points, rather than only a sequence of placements approaching optimality". My rationale here is that the current wording, although technically explained at a very low level, requires some thought if you haven't been exposed to the idea that an optimal solution may not actually exist (which can be counterintuitive for geometric shapes), and thus being explicit about that is helpful. Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • Ok, done. —David Eppstein (talk) 17:51, 20 April 2022 (UTC)
• "with two of the shaded shapes have area 1/8" Would it be possible to adjust the diagram to have the small triangles be shaded their own color? (What is the coloring scheme for in the first place) Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • Recolored and recaptioned. You may need to force a reload to see the modified image. —David Eppstein (talk) 18:06, 20 April 2022 (UTC)
    • Looks good. Ovinus (talk) 19:08, 20 April 2022 (UTC)
• Maybe include a brief explanation of how the optimal solution has been proven for 7 points. (Is it some sort of convex optimization problem?) Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • But the optimal solution (for the usual version of the problem in which the domain is a square) is not known for n=7. Do you mean, how to prove that the unit-area domain making the solution biggest leads to area 1/9? It's a messy case analysis. I didn't see a way to boil it down to a simple clear idea. —David Eppstein (talk) 18:15, 20 April 2022 (UTC)
    • The article does say "These constructions have been proven optimal for up to seven points", referring to the square, so that's correct, right? Ovinus (talk) 19:08, 20 April 2022 (UTC)
      • Oops, correct. For some reason the other sources I looked at in formulating that reply didn't mention this and I overlooked it in the article itself. I added a sentence about it. —David Eppstein (talk) 20:31, 20 April 2022 (UTC)
        • Great, and I quite like the new explanation. Will pass, since the "eye candy" of higher solution isn't necessary for GA (but would always be nice). Ovinus (talk) 20:58, 20 April 2022 (UTC)
• "For any two shapes D and D' " Only convex shapes. Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • The argument does not require convexity. It works as long as the two shapes are compact with nonempty interior, the same assumption made throughout this section. —David Eppstein (talk) 18:19, 20 April 2022 (UTC)
    • True, I suppose it's being pedantic given you say the most important cases is "convex set of nonzero area" early on. Ovinus (talk) 19:08, 20 April 2022 (UTC)
• "when stating bounds on how ... D is irrelevant and the subscript may be omitted" Er... only big-O bounds, yes? Is there a clearer way of phrasing that, maybe "bounds on (the order of) delta ..." Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • Only bounds accurate to within a constant factor. Some bounds of this type can be expressed using big O notation. Some cannot, and require big Omega notation. The idea of asymptotic analysis is more fundamental than the notation used to describe its bounds. This is what I was trying to get at with the existing phrasing, "bounds on how [Delta] grows as a function of n". I added something about constants of proportionality to clarify this point. —David Eppstein (talk) 18:30, 20 April 2022 (UTC)
• "instead about its asymptotic analysis" Probably just "asymptotic behavior" Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • Ok, used the redirect instead. —David Eppstein (talk) 18:30, 20 April 2022 (UTC)
• "the remaining low-area triangles are rare" Maybe say "rare (in a precise sense)" or something; otherwise people might think it has some general mathematical meaning
  • I changed "rare" to "few". There is a precise bound but stating it precisely would greatly obscure the point. —David Eppstein (talk) 18:31, 20 April 2022 (UTC)
    • Cool. And I didn't mean to include the full bound, just literally "(in a precise sense)", but it looks good now anyway. Ovinus (talk) 19:08, 20 April 2022 (UTC)
• Do optimal solutions necessarily have all points on the boundary? Are they necessarily rational? Ovinus (talk) 14:55, 19 April 2022 (UTC) Nvm, didn't see it in Specific shapes and numbers for some reason. Ovinus (talk) 18:14, 20 April 2022 (UTC)
• "It is easy to demonstrate" I generally don't like these constructions except for completely trivial statements. Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • The point was to contrast this demonstration, so easy that it can be done twice in the following two sentences, with Roth's less-easy bound. But whatever, I removed that phrase. Now it doesn't flow so well, though: "This is true. Roth proved that this other thing is true." —David Eppstein (talk) 18:34, 20 April 2022 (UTC)
    • I think it flows fine? "This is true. In 1951, Roth proved that a stronger result is true." Ovinus (talk) 19:08, 20 April 2022 (UTC)
• "for some constant c" Are any bounds on c known? Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • The source doesn't appear to state this. Think of it as like O-notation. You haven't asked what the hidden constants are in any of the earlier O- and Omega-notation bounds stated in this article; the all have "for some constant c" as part of their definition. What makes this one different?
    • True. I just didn't notice that the numerator was sublinear. Ovinus (talk) 19:08, 20 April 2022 (UTC)
• "Erdős's construction was published in Roth (1951), credited to Erdős" Is "credited to Erdos" necessary? Ovinus (talk) 14:55, 19 April 2022 (UTC)
  • That is in footnote c, which is intended as an explanatory footnote, explaining why we're saying that it is Erdős's construction but giving only a source to Roth and not to an original publication by Erdős. The explanation is that Roth is the only publication. We need to say that Roth credited the construction to Erdős to make clear that this is how we know it's Erdős's construction. If we just wrote that it was first published by Roth, readers might think that Roth somehow invented it independently and that we haven't said how we know that it was really by Erdős. —David Eppstein (talk) 18:41, 20 April 2022 (UTC)
• Perhaps link "3-uniform" to Hypergraph#Properties_of_hypergraphs
  • But MOS:SOB? —David Eppstein (talk) 18:42, 20 April 2022 (UTC)

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

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

Some specimen solutions

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)

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)

[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)

Actually, never mind, it's open access. They're on page 5. Ovinus (talk) 13:48, 20 April 2022 (UTC)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

I've lightened the heavy hatching. Maproom (talk) 21:49, 7 May 2022 (UTC)

... and used a footnote for the "non-congruent" thing. Maproom (talk) 08:25, 8 May 2022 (UTC)

Highlighted triangles in the gallery of optimal solutions

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)

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)

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)

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)