Heilbronn triangle problem

File:Heilbronn square n=6.svg

Solution to the Heilbronn triangle problem for six points in the unit square. These points form triangles of four different shapes, with minimum area 1/8, as large as possible for six points in the square. This solution is an affine transformation of a regular hexagon but larger numbers of points have solutions that include interior points of the square.

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 (possibly a degenerate one, with zero area). Let Δ(S) denote the minimum of the areas of these triangles, and let Δ(n) (for an integer n ≥ 3) denote the supremum of the values of Δ(S).

The question posed by Heilbronn was to give an expression, or matching asymptotic upper and lower bounds, for Δ(n). That is, the goal is to find a function f, described by a closed-form expression, and constants c₁ and c₂, such that for all n,

$c_1 f(n) \le \Delta(n) \le c_2 f(n)$.

In terms of big O notation, the left inequality may be written as Δ(n) = Ω(f(n)), the right inequality may be written as Δ(n) = O(f(n)), and both of them together may be written as Δ(n) = Θ(f(n)). The shape and area of D may affect the exact values of Δ(n), 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

$\Delta(n)=O\left(\frac{1}{n^2}\right).$

As Paul Erdős showed, no smaller bound is possible: when n is a prime number, the set of n points (i, i² mod n) 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/n², 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.

Komlós, Pintz & Szemerédi (1982) eventually disproved Heilbronn's conjecture, by finding sets of points whose smallest triangle area grows asymptotically as

$\Delta(n)=\Omega\left(\frac{\log n}{n^2}\right).$

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. Roth (1951) was the first to prove a nontrivial upper bound on Δ(n), of the form

$\Delta(n)=O\left(\frac{1}{n\sqrt{\log\log n}}\right).$

The best bound known to date is of the form

$\Delta(n)\leq\frac{\exp{\left(c\sqrt{\log n}\right)}}{n^{8/7}},$

for some constant c, proven by Komlós, Pintz & Szemerédi (1981).

Specific shapes and numbers

Goldberg (1972) 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, Comellas & Yebra (2002) 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 an argument based on Kolmogorov complexity shows 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.

External links

• Weisstein, Eric W., "Heilbronn Triangle Problem", MathWorld.
• Erich's Packing Center, by Erich Friedman, including the best known solutions to the Heilbronn problem for small values of n for squares, circles, equilateral triangles, and convex regions of variable shape but fixed area