Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T19:29:20.354Z Has data issue: false hasContentIssue false

The Exact Distribution of the Number of Vertices of a Random Convex Chain

Published online by Cambridge University Press:  21 December 2009

Christian Buchta
Affiliation:
Fachbereich Mathematik, Universität Salzburg, Hellbrunner Straße 34, A-5020 Salzburg, Austria.
Get access

Abstract

Assume that n points P1,…,Pn are distributed independently and uniformly in the triangle with vertices (0, 1), (0, 0), and (1, 0). Consider the convex hull of (0, 1), P1,…,Pn, and (1, 0). The vertices of the convex hull form a convex chain. Let be the probability that the convex chain consists – apart from the points (0, 1) and (1, 0) – of exactly k of the points P1,…,Pn. Bárány, Rote, Steiger, and Zhang [3] proved that . The values of are determined for k = 1,…,n − 1, and thus the distribution of the number of vertices of a random convex chain is obtained. Knowing this distribution provides the key to the answer of some long-standing questions in geometrical probability.

Type
Research Article
Copyright
Copyright © University College London 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Alagar, V. S., On the distribution of a random triangle. J. Appl. Prob. 14 (1977), 284297.CrossRefGoogle Scholar
2Bárány, I. and Reitzner, M., Random polytopes (manuscript).Google Scholar
3Bárány, I., Rote, G., Steiger, W. and Zhang, C.-H., A central limit theorem for convex chains in the square. Discrete Comput. Geom. 23 (2000), 3550.CrossRefGoogle Scholar
4Buchta, C., Zufallspolygone in konvexen Vielecken. J. reine angew. Math. 347 (1984), 212220.Google Scholar
5Buchta, C., On a conjecture of R. E. Miles about the convex hull of random points. Monatsh. Math. 102 (1986), 91102.CrossRefGoogle Scholar
6Buchta, C., On the distribution of the number of vertices of random polygon. Anz. Österr. Akad. Wiss., Math.-Naturwiss. Kl., Abt. II, 139 (2003), 1719.Google Scholar
7Buchta, C., An identity relating moments of functionals of convex hulls. Discrete Comput. Geom. 33 (2005), 125142.CrossRefGoogle Scholar
8Henze, N., Random triangles in convex regions. J. Appl. Prob. 20 (1983), 111125.CrossRefGoogle Scholar
9Reed, W. J., Random points in a simplex. Pacific J. Math. 54 (1974), 183198.CrossRefGoogle Scholar
10Valtr, P., Probability that n random points are in convex position. Discrete Comput. Geom. 13 (1995), 637643.CrossRefGoogle Scholar
11Valtr, P., The probability that n random points in a triangle are in convex position. Combinatorica 16 (1996), 567573.CrossRefGoogle Scholar
12Vu, V. H., Sharp concentration of random polytopes. Geom. Funct. Anal. 15 (2005), 12841318.CrossRefGoogle Scholar