Heilbronn triangle problem

Unsolved problem in mathematics

What is the asymptotic growth rate of the area of the smallest triangle determined by three out of $n$ points in a square, when the points are chosen to maximize this area?

More unsolved problems in mathematics

Six points in the unit square, with the smallest triangles (red) having area 1/8, the optimal area for this number of points. Other larger triangles are colored blue. These points are 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 asks how to place $n$ 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

The Heilbronn triangle problem concerns the placement of $n$ 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, and different placements make the smallest of these triangles larger or smaller. The problem asks: how should the $n$ points be placed to maximize the area of the smallest triangle?

More formally, the shape may be assumed to be a compact set $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, $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 an optimal placement of $n$ points, rather than only a sequence of placements approaching optimality. The number $\Delta _{D}(n)$ 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 have.

An example is shown in the figure, with six points in a unit square. These six points form ${\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, and the remaining 14 triangles have larger areas. This is the optimal placement of six points in a unit square: all other placements form at least one triangle with area 1/8 or smaller. Therefore, writing $\Delta _{\square }(n)$ for the case in which $D$ is the unit square, $\Delta _{\square }(6)={\tfrac {1}{8}}$.

Although researchers have studied the value of $\Delta _{D}(n)$ for specific shapes and specific small numbers of points, Heilbronn was concerned instead about its asymptotic behavior: if the shape $D$ is held fixed, but $n$ varies, how does the area of the smallest triangle vary with $n$? That is, Heilbronn's question concerns the growth rate of $\Delta _{D}(n)$, as a function of $n$. For any two convex shapes $D$ and $D'$ of nonzero area, the numbers $\Delta _{D}(n)$ and $\Delta _{D'}(n)$ differ by at most a constant factor, depending on the two shapes but not on $n$: some affine image of $D'$ is contained in $D$, and carrying a placement through it multiplies every triangle area by the same factor. Therefore, in bounds on the growth rate of $\Delta _{D}(n)$ that omit the constant of proportionality of that growth, the choice of $D$ is irrelevant and the subscript may be omitted.

This independence applies only to growth rates. For a fixed number of points, the exact value of $\Delta _{D}(n)$ depends on the shape, and three choices have been studied in detail. In the classical case $D$ is the unit square, $\Delta _{\square }(n)$. A second line of work takes $D$ to be a triangle of unit area, written $\Delta _{\triangle }(n)$. 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 of $\Delta _{D}(n)$. These three problems have different answers, and are treated separately below.

Heilbronn's conjecture and its disproof

Heilbronn conjectured prior to 1951 that $\Delta (n)$ always shrinks rapidly as a function of $n$, at a rate inversely proportional to the square of $n$. In terms of big O notation, this can be expressed as the bound $$\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 $\Omega (1/n^{2})$.

In the other direction, Paul Erdős found examples of point sets with minimum triangle area proportional to $1/n^{2}$, demonstrating that, if true, Heilbronn's conjectured bound could not be strengthened. These examples are also solutions to the no-three-in-line problem, which asks for large sets of grid points with no three in a line. As Erdős observed, when $n$ is a prime number, the set of $n$ points $(i,i^{2}{\bmod {n}})$ on an $n\times n$ integer grid (for $0\leq i<n$) has no three collinear points, and therefore by Pick's theorem each of the triangles formed by these points has area at least ${\tfrac {1}{2}}$. When these grid points are scaled to fit within a unit square, their smallest triangle area is proportional to $1/n^{2}$, matching Heilbronn's conjectured upper bound. If $n$ is not prime, then a similar construction using a prime number close to $n$ achieves the same asymptotic lower bound.

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 in the sets found by Erdős. Their construction involves the following steps:

• Randomly place $n^{1+\varepsilon }$ points in the unit square, for some $\varepsilon >0$.
• 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 to show that, with high probability, the remaining points include a subset of $n$ points that do not form any small-area triangles.

Their construction shows that $$\Delta (n)=\Omega \left({\frac {\log n}{n^{2}}}\right).$$ The proof can be derandomized, leading to a polynomial-time algorithm for constructing placements with this triangle area.

Upper bounds

Every set of $n$ points in the unit square contains three points forming a triangle of area at most proportional to $1/n$. 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 $x$-coordinates, and to choose the three consecutive points in this ordering whose $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 $\Delta (n)$, of the form $$\Delta (n)=O\left({\frac {1}{n{\sqrt {\log \log n}}}}\right).$$ A considerably stronger bound, $$\Delta (n)\leq {\frac {\exp {\left(c{\sqrt {\log n}}\right)}}{n^{8/7}}},$$ for some constant $c$, was proven by Komlós, Pintz & Szemerédi (1981) and stood for more than four decades.

Cohen, Pohoata & Zakharov (2023) gave the first improvement, an upper bound equal to $n^{-{\frac {8}{7}}-{\frac {1}{2000}}}$. 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: $$\Delta (n)\leq n^{-7/6+o(1)}.$$

Specific shapes and numbers

Unit square

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 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, Dehbi & Zeng (2022) combined numerical search with symbolic computation to show that $\Delta _{\square }(8)={\tfrac {{\sqrt {13}}-1}{36}}$. For nine points, Chen, Xu & Zeng (2017) obtained sharp bounds by an extensive branch-and-bound computation on CPU and GPU clusters. Subsequently, configurations that are globally optimal to within a certified numerical tolerance were computed for $n\leq 9$ using mixed-integer nonlinear optimization by Monji, Modir & Kocuk (2025), and refined analytically by Sudermann-Merx (2026) 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.

• 
  7 points in a square, all 8 minimal triangles shaded ($A\approx 0.0839$)
• 
  8 points in a square, 5 of 12 minimal triangles shaded ($A\approx 0.0724$)
• 
  9 points in a square, 6 of 11 minimal triangles shaded ($A\approx 0.0549$)
• 
  10 points in a square, 3 of 16 minimal triangles shaded ($A\approx 0.0465$)
• 
  11 points in a square, 8 of 28 minimal triangles shaded ($A\approx 0.0370$)
• 
  12 points in a square, 3 of 20 minimal triangles shaded ($A\approx 0.0326$)

Triangle

When the container is a triangle of unit area, exact values of $\Delta _{\triangle }(n)$ are known for small numbers of points. Here $\Delta _{\triangle }(4)={\tfrac {1}{3}}$, and $\Delta _{\triangle }(5)=3-2{\sqrt {2}}$, proven by Royce Peng in 1989. Yang, Zhang & Zeng (1994) proved that $\Delta _{\triangle }(6)={\tfrac {1}{8}}$. For seven points, Zeng & Chen (2019) proved that $\Delta _{\triangle }(7)={\tfrac {7}{72}}$, and that the optimal configuration is unique, by a symbolic analysis of eight cases. For eight points, Chen, Zeng & Zhou (2014) established an upper bound by a branch-and-bound search over octuples of subtriangles.

Convex shapes

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 $D$ with area one, the regular hexagon is the one that maximizes $\Delta _{D}(6)$, with $\Delta _{D}(6)={\tfrac {1}{6}}$ attained by placing the six points at the hexagon vertices. The convex shapes of unit area that maximize $\Delta _{D}(7)$ have $\Delta _{D}(7)={\tfrac {1}{9}}$. 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 parameter $k$, and asks for placements of $n$ points in the unit hypercube that maximize the minimum volume of the convex hull of any subset of $k$ points. For $k=d+1$ these subsets form simplices but for larger values of $k$, relative to $d$, they can form more complicated shapes. When $k$ is sufficiently large relative to $\log n$, randomly placed point sets have minimum $k$-point convex hull volume $\Omega (k/n)$. No better bound is possible; any placement has $k$ points with volume $O(k/n)$, obtained by choosing some $k$ 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

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