On the convex hull of random points in a polytope
- 1 December 1988
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 25 (4) , 688-699
- https://doi.org/10.2307/3214289
Abstract
The convex hull of n points drawn independently from a uniform distribution on the interior of a d-dimensional polytope is investigated. It is shown that the expected number of vertices is O(logd–1n) for any polytope, the expected number of vertices is Ω(logd–1n) for any simple polytope, and the expected number of facets is O(logd–1n) for any simple polytope. An algorithm is presented for constructing the convex hull of such sets of points in linear average time.Keywords
This publication has 15 references indexed in Scilit:
- Stochastical approximation of convex bodiesMathematische Annalen, 1985
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- Moment inequalities for random variables in computational geometryComputing, 1983
- A note on finding convex hulls via maximal vectorsInformation Processing Letters, 1980
- On the Average Number of Maxima in a Set of Vectors and ApplicationsJournal of the ACM, 1978
- Divide and conquer for linear expected timeInformation Processing Letters, 1978
- Die konvexe Hülle von n rotationssymmetrisch verteilten PunktenProbability Theory and Related Fields, 1970
- The convex hull of a random set of pointsBiometrika, 1965
- ber die konvexe H lle von n zuf llig gew hlten Punkten. IIProbability Theory and Related Fields, 1964
- ber die konvexe H lle von n zuf llig gew hlten PunktenProbability Theory and Related Fields, 1963