The Expected Size of Heilbronn's Triangles

Heilbronn's triangle problem asks for the least \Delta such that n points lying in the unit disc necessarily contain a triangle of area at most \Delta. Heilbronn initially conjectured \Delta = O(1=n 2 ). As a result of concerted mathematical effort it is currently known that there are positive constants c and C such that c log n=n 2 \Delta C=n 8=7\Gammaffl for every constant ffl ? 0. We resolve Heilbronn's problem in the expected case: If we uniformly at random put n points in the unit disc then the area of the smallest triangle has expectation \Theta(1=n 3 ) (and the smallest triangle has area \Theta(1=n 3 ) with probability almost one). Our proof uses the incompressibility method based on Kolmogorov complexity. 1 Introduction An old problem by Heilbronn is as follows: Let x 1 ; : : : ; xn be n points in the unit disc in the plane. Denote by A k (x 1 ; : : : ; xn ) the smallest area of all the polygons induced by the point sets fx i 1 ; : : : ; x i k g. Put g k (n) =..