The Average-Case Area of Heilbronn-Type Triangles
<|reference_start|>The Average-Case Area of Heilbronn-Type Triangles: From among $ {n \choose 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/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.''<|reference_end|>
@article{jiang1999the,
    title={The Average-Case Area of Heilbronn-Type Triangles},
    author={Tao Jiang (UCR), Ming Li (UCSB), Paul Vitanyi (CWI and U Amsterdam)},
    journal={T. Jiang, M. Li, and P. Vitanyi, The average-case area of
  Heilbronn-type triangles, Random Structures and Algorithms, 20:2(2002),
  206-219},
    year={1999},
    archivePrefix={arXiv},
    eprint={math/9902043},
    primaryClass={math.CO cs.CG cs.DM math.LO math.MG math.PR}
}