Mathematics – Combinatorics
Scientific paper
1999-02-05
T. Jiang, M. Li, and P. Vitanyi, The average-case area of Heilbronn-type triangles, Random Structures and Algorithms, 20:2(200
Mathematics
Combinatorics
13 pages, LaTeX, 1 figure,Popular treatment in D. Mackenzie, On a roll, {\em New Scientist}, November 6, 1999, 44--48
Scientific paper
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.''
Jiang Tao
Li Ming
Vitanyi Paul
No associations
LandOfFree
The Average-Case Area of Heilbronn-Type Triangles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Average-Case Area of Heilbronn-Type Triangles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Average-Case Area of Heilbronn-Type Triangles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-46853