Talk:Heilbronn triangle problem/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

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)