Premium
The average‐case area of Heilbronn‐type triangles *
Author(s) -
Jiang Tao,
Li Ming,
Vitányi Paul
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10024
Subject(s) - combinatorics , square (algebra) , unit square , mathematics , type (biology) , position (finance) , value (mathematics) , distribution (mathematics) , expected value , unit (ring theory) , geometry , mathematical analysis , statistics , ecology , mathematics education , finance , economics , biology
From among \documentclass{article}\pagestyle{empty}\begin{document}${n \choose 3}$\end{document} 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 <μ n < C / n 3 for all large enough values of n , where μ 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.” © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 206–219, 2002