A Deterministic Polynomial-Time Algorithm for Heilbronn's Problem in Three Dimensions
Hanno Lefmann, Niels Schmitt · SIAM Journal on Computing · 2002
Heilbronn conjectured that among arbitrary n points in the two-dimensional unit square [0,1] 2 , there must be three points which form a triangle of area O(1/n 2 ). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz, and Szemerédi [J. London Math. Soc., 25 (1982), pp. 13--24], who showed that for every n there exists a configuration of n points in the unit square [0,1] 2 where all triangles have area $\Omega({\log n}/{n^2})$. Here we will consider a three-dimensional analogue of this problem and show how to find deterministically in polynomial time n points in the unit cube [0,1] 3 such that the volume of every tetrahedron among these n points is $\Omega(\log n/n^3)$.