Heilbronn triangle problem
In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area.
It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points.
His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.
points be placed to maximize the area of the smallest triangle?
in the plane, meaning that it stays within a bounded distance from the origin and that points are allowed to be placed on its boundary.
When three of the placed points lie on a line, they are considered as forming a degenerate triangle whose area is defined to be zero, so placements that maximize the smallest triangle will not have collinear triples of points.
The assumption that the shape is compact implies that there exists an optimal placement of
may be defined as the area of the smallest triangle in this optimal placement.
[1][a] An example is shown in the figure, with six points in a unit square.
[1] Heilbronn conjectured prior to 1951 that the minimum triangle area always shrinks rapidly as a function of
[1][b] 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 to
, 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.
) have no three collinear points, and therefore by Pick's formula each of the triangles they form has area at least
When these grid points are scaled to fit within a unit square, their smallest triangle area is proportional to
[1][c] 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.
The proof can be derandomized, leading to a polynomial-time algorithm for constructing placements with this triangle area.
points in the unit square forms a triangle of area at most inversely proportional to
One way to see this is to triangulate the convex hull of the given point set
In the first paper published on the Heilbronn triangle problem, in 1951, Klaus Roth proved a stronger upper bound on
[2] Goldberg's constructions for up to six points lie on the boundary of the square, and are placed to form an affine transformation of the vertices of a regular polygon.
, Comellas & Yebra (2002) improved Goldberg's bounds, and for these values the solutions include points interior to the square.
The proof used a computer search to subdivide the configuration space of possible arrangements of the points into 226 different subproblems, and used nonlinear programming techniques to show that in 225 of those cases, the best arrangement was not as good as the known bound.
, with six points optimally placed at the hexagon vertices.
[11] There have been many variations of this problem including the case of a uniformly random set of points, for which arguments based on either Kolmogorov complexity or Poisson approximation show that the expected value of the minimum area is inversely proportional to the cube of the number of points.
[12][13] Variations involving the volume of higher-dimensional simplices have also been studied.
[14][15][16] Rather than considering simplices, another higher-dimensional version adds another parameter
points in the unit hypercube that maximize the minimum volume of the convex hull of any subset of
This result has applications in range searching data structures.
