Heilbronn triangle problem


In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points within a region in the plane, in order to avoid triangles of small area. It is named after Hans Heilbronn, who conjectured prior to 1950 that this smallest triangle area is necessarily at most inversely proportional to the square of the number of points. Heilbronn's conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.

Definition

The problem may be defined in terms of any compact set D in the plane with nonzero area such as the unit square or the unit disk. If S is a set of n points of D, then every three points of S determine a triangle. Let Δ denote the minimum of the areas of these triangles, and let Δ denote the supremum of the values of Δ.
The question posed by Heilbronn was to give an expression, or matching asymptotic upper and lower bounds, for Δ. That is, the goal is to find a function f, described by a closed-form expression, and constants c1 and c2, such that for all n,
In terms of big O notation, the left inequality may be written as Δ = Ω, the right inequality may be written as Δ = O, and both of them together may be written as Δ = Θ. The shape and area of D may affect the exact values of Δ, but only by a constant factor, so they are unimportant for its asymptotic growth rate.

Heilbronn's conjecture and lower bound constructions

Heilbronn conjectured that
As Paul Erdős showed, no smaller bound is possible: when n is a prime number, the set of n points on an n × n integer grid have no three collinear points, and therefore by Pick's formula each of the triangles they form has area at least 1/2. When this set of grid points is scaled to a unit square, they form a set of points whose smallest triangle area is at least proportional to 1/n2, matching Heilbronn's conjectured upper bound.
If n is not prime, then a similar construction using the next prime number larger than n achieves the same asymptotic lower bound.
eventually disproved Heilbronn's conjecture, by finding sets of points whose smallest triangle area grows asymptotically as

Upper bounds

Trivially, either by triangulating the convex hull of the given point set S or by choosing consecutive triples of points in the sorted order of their x-coordinates, it is possible to show that every point set contains a small triangle, whose area is at most inversely proportional to n. was the first to prove a nontrivial upper bound on Δ, of the form
The best bound known to date is of the form
for some constant c, proven by.

Specific shapes and numbers

has investigated the optimal arrangements of n points in a square, for n 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 of n, 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 seven points.

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.