|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
The Average-Case Area of Heilbronn-Type Triangles | | Tao Jiang
; Ming Li
; Paul Vitanyi
; | | Date: |
5 Feb 1999 | | 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 | | Subject: | Combinatorics; Logic; Metric Geometry; Probability; Computational Geometry; Discrete Mathematics MSC-class: 52C10 | math.CO cs.CG cs.DM math.LO math.MG math.PR | | Affiliation: | UCR), Ming Li (UCSB), Paul Vitanyi (CWI and U Amsterdam | | Abstract: | 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.’’ | | Source: | arXiv, math.CO/9902043 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER