Open problem, Geometry, posed 1950

Heilbronn triangle problem

Open

For $n \ge 3$ points placed inside a compact convex region of area $1$ in the plane (such as the unit square $[0,1]^2$ or the unit-area disk), let $\Delta(n)$ denote the supremum over all $n$ -point configurations of the minimum area of a triangle formed by three of the points. Determine the asymptotic order of growth of $\Delta(n)$ as $n \to \infty$ .

Research frontier as of 2026

As of 2026, the Heilbronn triangle problem remains wide open, with a large polynomial gap between the best known lower bound $\Delta(n) = \Omega(\log n / n^2)$ (Komlós–Pintz–Szemerédi, 1982) and the best known upper bound $\Delta(n) \le n^{-7/6 + o(1)}$ (Cohen–Pohoata–Zakharov, 2024, `arXiv:2409.07658`). After Komlós, Pintz, and Szemerédi established $\Delta(n) \le n^{-8/7 + o(1)}$ in 1981, the upper bound exponent $8/7 \approx 1.1429$ stood unchanged for over forty years until Cohen, Pohoata, and Zakharov (`arXiv:2305.18253`, 2023) improved it to $8/7 + 1/2000$ and subsequently to $7/6 \approx 1.1667$ in 2024 by reframing Roth's strip argument in terms of multiscale incidences between points and $\delta$ -tubes.

Best known results

Upper bound: $\Delta(n) \le n^{-7/6 + o(1)}$ (Alex Cohen, Cosmin Pohoata, and Dmitrii Zakharov, 2024, `arXiv:2409.07658`).
Lower bound: $\Delta(n) = \Omega(\log n / n^2)$ (János Komlós, János Pintz, and Endre Szemerédi, 1982).

Tools and where they stop

Tool	Achieved	Where it stops
High-low Fourier method and multiscale point-tube incidences (Cohen–Pohoata–Zakharov)	Converts the absence of small-area triangles into lower bounds on incidences between points and narrow strips ( $\delta$ -tubes) across scales, improving the upper bound exponent from $8/7$ to $7/6$ .	Two-step incidence arguments only track pairs of points and the strips they determine; reaching exponents near $2$ would require controlling higher-order multi-point correlations.
Semi-random hypergraph independence (Ajtai–Komlós–Pintz–Spencer–Szemerédi)	Finds an independent set in a $3$ -uniform hypergraph of small-area triples with few short cycles, gaining an extra $\log n$ factor over Erdős's $1/n^2$ construction.	At area threshold $\gg \log n / n^2$ , triangles in the hypergraph share edges and form dense local clusters that break the uncrowded hypergraph condition.

Open questions

Is the true asymptotic order of $\Delta(n)$ equal to $\Theta(\log n / n^2)$ , or can configurations achieve $\Delta(n) \ge n^{-2 + \delta}$ for some $\delta > 0$ ?

References

János Komlós, János Pintz, Endre Szemerédi (1982). A lower bound for Heilbronn's problem · DOI:10.1112/jlms/s2-25.1.13
Alex Cohen, Cosmin Pohoata, Dmitrii Zakharov (2023). A new upper bound for the Heilbronn triangle problem · arXiv:2305.18253
Alex Cohen, Cosmin Pohoata, Dmitrii Zakharov (2024). Lower bounds for incidences · arXiv:2409.07658 [preprint, not peer-reviewed]