triangle vary That is, Heilbronn's question concerns the growth rate as a function For any two shapes the numbers and differ only by a constant factor, as any placement of points within can be scaled by an affine transformation to fit changing the minimum triangle area only by a constant. Therefore, in bounds on the growth rate of that omit the constant of proportionality of that growth, the choice of is irrelevant and the subscript may be Heilbronn's conjecture and its disproof Heilbronn conjectured prior to 1951 that the minimum triangle area always shrinks rapidly as a function —more specifically, inversely proportional to the square In terms of big O notation, this can be expressed as the bound In the other direction, Paul Erdős found examples of point sets with minimum triangle area proportional 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 is a prime number, the set of points on an integer grid (for have no three collinear points, and therefore by Pick's formula each of the triangles they form has area at When these grid points are scaled to fit within a unit square, their smallest triangle area is proportional matching Heilbronn's conjectured upper bound. If is not prime, then a similar construction using a prime number close to achieves the same asymptotic lower 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 points in the unit square, for 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 hypergraphs of high girth to show that, with high probability, the remaining points include a subset of points that do not form any small-area triangles. The area resulting from their construction grows asymptotically as The proof can be derandomized, leading to a polynomial-time algorithm for constructing placements with this triangle area. Upper bounds Every set of points in the unit square forms a triangle of area at most