The Average-Case Area of Heilbronn-Type Triangles

Simple item page
dc.creatorJiang, Tao
dc.creatorLi, Ming
dc.creatorVitanyi, Paul
dc.date1999-02-05
dc.date2003-11-10
dc.date.accessioned2026-07-07T05:27:49Z
dc.date.available2026-07-07T05:27:49Z
dc.descriptionFrom 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 < μ_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.''
dc.description13 pages, LaTeX, 1 figure,Popular treatment in D. Mackenzie, On a roll, {\em New Scientist}, November 6, 1999, 44--48
dc.identifierhttps://arxiv.org/abs/math/9902043
dc.identifierhttp://arxiv.org/abs/math/9902043
dc.identifierT. Jiang, M. Li, and P. Vitanyi, The average-case area of Heilbronn-type triangles, Random Structures and Algorithms, 20:2(2002), 206-219
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/78066
dc.subjectCombinatorics
dc.subjectComputational Geometry
dc.subjectDiscrete Mathematics
dc.subjectLogic
dc.subjectMetric Geometry
dc.subjectProbability
dc.subject52C10
dc.titleThe Average-Case Area of Heilbronn-Type Triangles
dc.typetext

Files

Collections

arXiv