Talk:Heilbronn triangle problem

Heilbronn triangle problem has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it.
Review: April 20, 2022. (Reviewed version).

Mathematics GA‑class

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
GA	This article has been rated as GA-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's priority scale.

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

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

"some triangle will have an" Maybe just "the smallest triangle will have an" Ovinus (talk) 14:55, 19 April 2022 (UTC)[reply]
- Changed to "the smallest triangle area will be" —David Eppstein (talk) 17:49, 20 April 2022 (UTC)[reply]
"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)[reply]
- 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)[reply]
  - True. Ovinus (talk) 19:08, 20 April 2022 (UTC)[reply]
"The assumption that the shape is compact implies that there exists a placement of $n$ $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$ $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)[reply]
- Ok, done. —David Eppstein (talk) 17:51, 20 April 2022 (UTC)[reply]
"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)[reply]
- Recolored and recaptioned. You may need to force a reload to see the modified image. —David Eppstein (talk) 18:06, 20 April 2022 (UTC)[reply]
  - Looks good. Ovinus (talk) 19:08, 20 April 2022 (UTC)[reply]
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)[reply]
- 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)[reply]
  - 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)[reply]
    - 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)[reply]
      - 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)[reply]
"For any two shapes D and D' " Only convex shapes. Ovinus (talk) 14:55, 19 April 2022 (UTC)[reply]
- 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)[reply]
  - 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)[reply]
"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)[reply]
- 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)[reply]
"instead about its asymptotic analysis" Probably just "asymptotic behavior" Ovinus (talk) 14:55, 19 April 2022 (UTC)[reply]
- Ok, used the redirect instead. —David Eppstein (talk) 18:30, 20 April 2022 (UTC)[reply]
"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)[reply]
  - 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)[reply]
~~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)[reply]
"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)[reply]
- 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)[reply]
  - 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)[reply]
"for some constant c" Are any bounds on c known? Ovinus (talk) 14:55, 19 April 2022 (UTC)[reply]
- 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)[reply]
"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)[reply]
- 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)[reply]
Perhaps link "3-uniform" to Hypergraph#Properties_of_hypergraphs
- But MOS:SOB? —David Eppstein (talk) 18:42, 20 April 2022 (UTC)[reply]

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

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]