Heilbronn triangle problem

Optimal solution to the Heilbronn triangle problem for six points in the unit square. These points form triangles 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 for larger numbers of points the optimal solution does not form a convex polygon.

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 that, no matter how these points are placed, some triangle will have an area that is 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.

Definition[]

The Heilbronn triangle problem concerns the placement of ${\displaystyle n}$ points within a shape in the plane, such as the unit square or the unit disk, for a given number ${\displaystyle n}$, and the triangles determined by triples of points. Different placements of points will have different minimum-area triangles, and the problem asks: how should ${\displaystyle n}$ points be placed, in order to maximize the area of the smallest of these triangles?^[1]

More formally, the shape may be assumed to be a compact set ${\displaystyle D}$ 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. In most work on this problem, ${\displaystyle D}$ 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 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 a placement a placement of ${\displaystyle n}$ points whose minimum triangle area is at least as large as for any other placement. The number ${\displaystyle \Delta _{D}(n)}$ 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. These six points form ${\displaystyle {\tbinom {6}{3}}=20}$ different triangles, four of which are shaded in the figure. Six of these 20 triangles, with two of the shaded shapes, have area 1/8; the remaining 14 triangles have larger areas. This is the optimal placement of six points in a unit square: all other placements form a triangle with area 1/8 or smaller. Therefore, ${\displaystyle \Delta _{D}(6)={\tfrac {1}{8}}}$.^[2]

Although researchers have studied the value of ${\displaystyle \Delta _{D}(n)}$ for specific shapes and specific small numbers of points,^[2][3][4] Heilbronn was concerned instead about its asymptotic analysis: if the shape ${\displaystyle D}$ is held fixed, but ${\displaystyle n}$ varies, how does the area of the smallest triangle vary with ${\displaystyle n}$? That is, Heilbronn's question concerns the growth rate of ${\displaystyle \Delta _{D}(n)}$, as a function of ${\displaystyle n}$. For any two shapes ${\displaystyle D}$ and ${\displaystyle D'}$, the numbers ${\displaystyle \Delta _{D}(n)}$ and ${\displaystyle \Delta _{D'}(n)}$ differ only by a constant factor, as any placement of ${\displaystyle n}$ points within ${\displaystyle D}$ can be scaled by an affine transformation to fit within ${\displaystyle D'}$, changing the minimum triangle area only by a constant. Therefore, when stating bounds on how ${\displaystyle \Delta _{D}(n)}$ grows as a function of ${\displaystyle n}$, the choice of ${\displaystyle D}$ is irrelevant and the subscript may be omitted.^[1]

Heilbronn's conjecture and its disproof[]

Heilbronn conjectured prior to 1951 that the minimum triangle area always shrinks rapidly as a function of ${\displaystyle n}$, inversely proportional to the square of ${\displaystyle n}$.^[1][b] In terms of big O notation, this can be expressed as the bound

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

Solutions to the no-three-in-line problem, large sets of grid points with no three collinear points, can be scaled into a unit square with minimum triangle area ${\displaystyle \Omega (1/n^{2})}$.

In the other direction, Paul Erdős found examples of point sets with minimum triangle area proportional to ${\displaystyle 1/n^{2}}$, 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 ${\displaystyle n}$ is a prime number, the set of ${\displaystyle n}$ points ${\displaystyle (i,i^{2}{\bmod {n}})}$ on an ${\displaystyle n\times n}$ integer grid (for ${\displaystyle 0\leq i<n}$) have no three collinear points, and therefore by Pick's formula each of the triangles they form has area at least ${\displaystyle {\tfrac {1}{2}}}$. When these grid points are scaled to fit within a unit square, their smallest triangle area is proportional to ${\displaystyle 1/n^{2}}$, matching Heilbronn's conjectured upper bound. If ${\displaystyle n}$ is not prime, then a similar construction using a prime number close to ${\displaystyle n}$ achieves the same asymptotic lower bound.^[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. Their construction involves the following steps:

• Randomly place ${\displaystyle n^{1+\varepsilon }}$ points in the unit square, for some ${\displaystyle \varepsilon >0}$.
• Remove all pairs of points that are unexpectedly close together.
• Prove that, because the remaining low-area triangles are rare, there are only a sublinear number of cycles formed by two, three, or four low-area triangles, and 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 ${\displaystyle n}$ points that do not form any small-area triangles.

The area resulting from their construction grows asymptotically as^[5]

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

Upper bounds[]

It is easy to demonstrate that every set of ${\displaystyle n}$ points in the unit square forms a triangle of area at most inversely proportional to ${\displaystyle n}$. One way to see this is to triangulate the convex hull of the given point set ${\displaystyle S}$, and choose the smallest of the triangles in the triangulation. Another is to sort the points by their ${\displaystyle x}$-coordinates, and to choose the three consecutive points in this ordering whose ${\displaystyle x}$-coordinates are the closest together. In the first paper published on the Heilbronn triangle problem, in 1951, Klaus Roth proved a stronger upper bound on ${\displaystyle \Delta (n)}$, of the form^[1]

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

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

constant ${\displaystyle c}$,

Specific shapes and numbers[]

Goldberg (1972) has investigated the optimal arrangements of ${\displaystyle n}$ points in a square, for ${\displaystyle n}$ up to 16.^[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. For larger values of ${\displaystyle n}$, Comellas & Yebra (2002) improved Goldberg's bounds, and for these values the solutions include points interior to the square.^[3] These constructions have been proven optimal for up to seven points.^[4]

Instead of looking for optimal placements for a given shape, one may look for an optimal shape for a given number of points. Among convex shapes ${\displaystyle D}$ with area one, the regular hexagon is the one that maximizes ${\displaystyle \Delta _{D}(6)}$; for this shape, ${\displaystyle \Delta _{D}(6)={\tfrac {1}{6}}}$, with six points optimally placed at the hexagon vertices.^[8] The convex shapes of unit area that maximize ${\displaystyle \Delta _{D}(7)}$ have ${\displaystyle \Delta _{D}(7)={\tfrac {1}{9}}}$.^[9]

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.^[10][11] Variations involving the volume of higher-dimensional simplices have also been studied.^[12][13][14]

Rather than considering simplices, another higher-dimensional version adds another parameter ${\displaystyle k}$, and asks for placements of ${\displaystyle n}$ points in the unit hypercube that maximize the minimum volume of the convex hull of any subset of ${\displaystyle k}$ points. For ${\displaystyle k=d+1}$ these subsets form simplices but for larger values of ${\displaystyle k}$, relative to ${\displaystyle d}$, they can form more complicated shapes. When ${\displaystyle k}$ is sufficiently large relative to ${\displaystyle \log n}$, randomly placed point sets have minimum ${\displaystyle k}$-point convex hull volume ${\displaystyle \Omega (k/n)}$. No better bound is possible; any placement has ${\displaystyle k}$ points with volume ${\displaystyle O(k/n)}$, obtained by choosing some ${\displaystyle k}$ consecutive points in coordinate order. This result has applications in range searching data structures.^[15]

See also[]

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

Notes[]

References[]

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 ${\displaystyle n}$ for squares, circles, equilateral triangles, and convex regions of variable shape but fixed area