From among (n/3) 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/n3 < μn < C/n3 for all large enough values of n, where μn is the expectation of A. Moreover, c/n3 < A < C/n3, 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." © 2002 Wiley Periodicals, Inc.

The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas (Li and Vitányi, An Introduction to Kolmogorov Complexity and its Applications, Springer, New York, 1997). To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method. © 2000 Elsevier Science B.V. All rights reserved.