The Average-Case Area of Heilbronn-Type Triangles

Abstract

From among $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ triangles with vertices chosen from $n$ points in the unit square, let $T$ be the one with the smallest area, and let $A$ be the area of $T$. Heilbronn's triangle problem asks for the maximum value assumed by $A$ over all choices of $n$ points. We consider the average-case: If the $n$ points are chosen independently and at random (with a uniform distribution), then there exist positive constants $c$ and $C$ such that $c/n^3<{\mu }_n<C/n^3$ for all large enough values of $n$, where ${\mu }_n$ is the expectation of $A$. Moreover, $c/n^3<A<C/n^3$, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in ``general position.''

13 pages, LaTeX, 1 figure,Popular treatment in D. Mackenzie, On a roll, {\em New Scientist}, November 6, 1999, 44--48