Editing Heilbronn triangle problem (section)

==Heilbronn's conjecture and its disproof==
Heilbronn conjectured prior to 1951 that the minimum triangle area always shrinks rapidly as a function {{nowrap|of <math>n</math>}}—more specifically, inversely proportional to the square {{nowrap|of <math>n</math>.{{r|roth}}{{efn|The conjecture is credited to Heilbronn in {{harvtxt|Roth|1951}}, but without citation to any specific publication.}}}} In terms of [[big O notation]], this can be expressed as the bound
<math display=block>\Delta(n)=O\left(\frac{1}{n^2}\right).</math>
[[File:No-three-in-line.svg|thumb|upright=0.8|Solutions to the [[no-three-in-line problem]], large sets of grid points with no three collinear points, can be scaled into a unit square with minimum triangle area {{nowrap|<math>\Omega(1/n^2)</math>.}}]]
In the other direction, [[Paul Erdős]] found examples of point sets with minimum triangle area proportional {{nowrap|to <math>1/n^2</math>,}} demonstrating that, if true, Heilbronn's conjectured bound could not be strengthened. Erdős formulated the [[no-three-in-line problem]], on large sets of grid points with no three in a line, to describe these examples. As Erdős observed, when <math>n</math> is a [[prime number]], the set of <math>n</math> points <math>(i,i^2\bmod n)</math> on an <math>n\times n</math> [[integer lattice|integer grid]] (for {{nowrap|<math>0\le i<n</math>)}} have no three collinear points, and therefore by [[Pick's formula]] each of the triangles they form has area at {{nowrap|least <math>\tfrac12</math>.}} When these grid points are scaled to fit within a unit square, their smallest triangle area is proportional {{nowrap|to <math>1/n^2</math>,}} matching Heilbronn's conjectured upper bound. If <math>n</math> is not prime, then a similar construction using a prime number close to <math>n</math> achieves the same asymptotic lower {{nowrap|bound.{{r|roth}}{{efn|Erdős's construction was published in {{harvtxt|Roth|1951}}, credited to Erdős.}}}}

{{harvtxt|Komlós|Pintz|Szemerédi|1982}} eventually disproved Heilbronn's conjecture, by using the [[probabilistic method]] to find sets of points whose smallest triangle area is larger than the ones found by Erdős. Their construction involves the following steps:
*Randomly place <math>n^{1+\varepsilon}</math> points in the unit square, for {{nowrap|some <math>\varepsilon>0</math>.}}
*Remove all pairs of points that are unexpectedly close together.
*Prove that there are few remaining low-area triangles and therefore only a sublinear number of cycles formed by two, three, or four low-area triangles. Remove all points belonging to these cycles.
*Apply a [[triangle removal lemma]] for 3-uniform [[hypergraph]]s of high [[girth (graph theory)|girth]] to show that, with high probability, the remaining points include a subset of <math>n</math> points that do not form any small-area triangles.
The area resulting from their construction grows asymptotically as{{r|kps82}}
<math display=block>\Delta(n)=\Omega\left(\frac{\log n}{n^2}\right).</math>
The proof can be [[Derandomization|derandomized]], leading to a [[polynomial time|polynomial-time]] algorithm for constructing placements with this triangle area.{{r|bkhl}}