In discrete geometry and discrepancy theory, the Heilbronn triangle problem points in a region of the plane, such as a square, so that the smallest of the triangles formed by triples of the points is as large as possible. It is named after Hans Heilbronn, who conjectured that this largest achievable area shrinks at least as quickly as the inverse square of the number of points. Komlós, Pintz, and Szemerédi disproved the conjecture in 1982, finding placements whose smallest triangle is larger by a logarithmic factor, but the asymptotic growth rate of the area remains unknown.

Definition

points within a shape in the plane, such as the unit square or the unit disk. Each triple of the placed points forms a triangle points be placed to maximize the area of the smallest

More formally, the shape may be assumed to be a compact set is additionally a convex set of nonzero area. When three of the placed points lie on a line, they are considered as forming a degenerate may be defined as the area of the smallest triangle in such an optimal placement, that is, the largest area that the smallest triangle can be made to

is the unit square,

for specific shapes and specific small numbers of points, Heilbronn was concerned instead about its asymptotic behavior varies, how does the area of the smallest triangle vary That is, Heilbronn's question concerns the growth rate as a function differ by at most a constant factor, depending on the two shapes but not some affine image is contained that omit the constant of proportionality is irrelevant and the subscript may be

is the unit . Because any two triangles are related by an affine transformation, which scales all areas by the same factor, the particular triangle chosen does not affect the value. In a third variant the shape is not fixed in advance: among all convex shapes of unit area, one asks which admits the largest value These three problems have different answers, and are treated separately below.

Heilbronn's conjecture and its disproof

always shrinks rapidly as a function at a rate inversely proportional to the square In terms of big O notation 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. These examples are also solutions to the no-three-in-line problem is a prime number integer grid (for has no three collinear points, and therefore by Pick's theorem each of the triangles formed by these points has area at When these grid points are scaled to fit within a unit square, their smallest triangle area is proportional 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 in the sets found by Erdős. Their construction involves the following steps:

• 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 points that do not form any small-area triangles.

Their construction shows that The proof can be derandomized, leading to a polynomial-time algorithm for constructing placements with this triangle area.

Upper bounds

points in the unit square contains three points forming a triangle of area at most proportional One way to see this is to triangulate the convex hull of the points, and choose the smallest of the triangles in the triangulation. Another is to sort the points by their and to choose the three consecutive points in this ordering whose are the closest together. In the first paper published on the Heilbronn triangle problem, in 1951, Klaus Roth proved a stronger upper bound of the form for some was proven by and stood for more than four

gave the first improvement, an upper bound equal to The same authors subsequently obtained the strongest bound known to date, as a consequence of a lower bound on the number of incidences between points and tubes:

Specific shapes and numbers

Unit square

up to 16. 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. For larger values improved Goldberg's bounds, and for these values the solutions include points interior to the square.

These constructions have been proven optimal for up to eight points. For seven points, 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. In the remaining case, including the eventual optimal solution, its optimality was proven using symbolic computation techniques. For eight points, combined numerical search with symbolic computation to show For nine points, obtained sharp bounds by an extensive branch-and-bound computation on CPU and GPU clusters. using mixed-integer nonlinear optimization by , and refined analytically by into exact coordinates, recovering the configurations found by Comellas and Yebra.

The following are the best known solutions for 7–12 points in a unit square, found through simulated annealing. Those for seven and eight points are known to be optimal.

Triangle

, proven by Royce Peng in 1989. proved For seven points, proved and that the optimal configuration is unique, by a symbolic analysis of eight cases. For eight points, established an upper bound by a branch-and-bound search over octuples of subtriangles.

Convex shapes

with area one, the regular hexagon is the one that with attained by placing the six points at the hexagon vertices. have These are the only two numbers of points for which this variant has been settled. For larger numbers of points, configurations found numerically, without proofs of optimality, have been collected by Erich Friedman.

Variations

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. Variations involving the volume of higher-dimensional simplices have also been studied.

Rather than considering simplices, another higher-dimensional version adds another points in the unit hypercube that maximize the minimum volume of the convex hull these subsets form simplices but for larger values relative is sufficiently large relative randomly placed point sets have minimum convex hull points with consecutive points in coordinate order. This result has applications in range searching data structures.

See also

• Danzer set, a set of points that avoids empty triangles of large area

Notes

References

External links

• Erich's Packing Center for squares, circles, equilateral triangles, and convex regions of variable shape but fixed area