Convex and discrete geometry Discrete and combinatorial geometry Problem

Heilbronn triangle problem

Problem

Let $n \ge 3$ and let $P$ be a set of $n$ points in the unit square $[0, 1]^2$ . Let $\delta(P)$ be the smallest area of a triangle whose vertices are three points of $P$ . Three collinear points count as a triangle of area $0$ . Let $\Delta(n)$ be the supremum of $\delta(P)$ over all such $P$ . Determine the order of growth of $\Delta(n)$ as $n \to \infty$ .

Remarks

Hans Heilbronn conjectured that $\Delta(n) = O(1/n^2)$ , with $O$ the big O notation; the problem first appeared in print in a 1951 paper of Klaus Roth. Erdős showed $\Delta(n) \ge c/n^2$ for a constant $c > 0$ , so $1/n^2$ would be the right order. Komlós, Pintz and Szemerédi disproved the conjecture in 1982 by showing $\Delta(n) \ge c \log n / n^2$ . On the other side, Roth proved $\Delta(n) = o(1/n)$ , and Komlós, Pintz and Szemerédi proved $\Delta(n) \le n^{-8/7 + o(1)}$ in 1981. In 2023 Cohen, Pohoata and Zakharov improved the exponent $-8/7$ for the first time. The exact order of growth remains open.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`XT32T13KBY`
URI	`m2://XT32T13KBY`
Kind	problem
Writing	W0 stub
MSC	52C10, 51M04
Status	This copy of the site has no build data. Run `m2 status XT32T13KBY`.
About	Triangle
Uses	Triangle, Big O notation
Same as	Wikidata Q5699425 Wikipedia Heilbronn triangle problem

Heilbronn triangle problem

Problem

Remarks

Reading path

Further reading

What this page needs for W1

What links here