Name
Abstract | ||
|---|---|---|
From among ??? 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." |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1002/rsa.10024 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
heilbronn-type triangle,positive constants c,t. heilbronn,incompressibility method,n point,average-case area,general position,n c,smallest triangle,kolmogorov complexity,smallest area,triangle problem,uniform distribution | Journal | 20 |
Issue | ISSN | Citations |
2 | T. Jiang, M. Li, and P. Vitanyi, The average-case area of
Heilbronn-type triangles, Random Structures and Algorithms, 20:2(2002),
206-219 | 10 |
PageRank | References | Authors |
0.77 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tao Jiang | 1 | 1809 | 155.32 |
| Ming Li | 2 | 5595 | 829.00 |
| Paul Vitányi | 3 | 2130 | 287.76 |