Abstract
This paper studies the convex hull of n random points in \(\mathsf{R}^{d}\) . A recently proved topological identity of the author is used in combination with identities of Efron and Buchta to find the expected number of vertices of the convex hull—yielding a new recurrence formula for all dimensions d. A recurrence for the expected number of facets and (d−2)-faces is also found, this analysis building on a technique of Rényi and Sulanke. Other relationships for the expected count of i-faces (1≤i<d) are found when d≤5, by applying the Dehn–Sommerville identities. A general recurrence identity (see (3) below) for this expected count is conjectured.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Affentranger, F.: Generalization of a formula of C. Buchta about the convex hull of random points. Elem. Math. 43, 39–45, 151–152 (1988)
Badertscher, E.: An explicit formula about the convex hull of random points. Elem. Math. 44, 104–106 (1989)
Buchta, C.: Über die konvexe Hülle von Zufallspunkten in Eibereichen. Elem. Math. 38, 153–156 (1983)
Buchta, C.: Distribution-independent properties of the convex hull of random points. J. Theory Probab. 3, 387–393 (1990)
Buchta, C.: An identity relating moments of functions of convex hulls. Discrete Comput. Geom. 33, 125–142 (2005)
Buchta, C., Reitzner, M.: Equiaffine inner parallel curves of a plane convex body and the convex hulls of randomly chosen points. Probab. Theory Relat. Fields 108, 385–415 (1997)
Buchta, C., Reitzner, M.: The convex hull of random points in a tetrahedron: Solution of Blaschke’s problem and more general results. J. Reine Angew. Math. 536, 1–29 (2001)
Cowan, R.: Identities linking volumes of convex hulls. Adv. Appl. Probab. 39, 630–644 (2007)
Cowan, R., Chiu, S.N.: Extension of Deltheil’s study on random points in a convex quadrilateral. Adv. Appl. Probab. 37, 857–858 (2005)
Dehn, M.: Die Eulersche Formel in Zusammenhang mit dem Inhalt in der nicht-Euklidischen Geometrie. Math. Ann. 61, 561–586 (1905)
Efron, B.: The convex hull of a random set of points. Biometrika 52, 331–343 (1965)
Grünbaum, B.: Convex Polytopes, 2nd edn. Springer, Berlin (2003). Prepared by Kaibel, V., Klee, V. and Ziegler, G.M.
Kingman, J.F.C.: Random secants of a convex body. J. Appl. Probab. 6, 660–672 (1969)
Miles, R.E.: Isotropic random simplices. Adv. Appl. Probab. 3, 353–382 (1971)
Rényi, A., Sulanke, R.: Über die konvexe Hülle von n zufällig gewählten Punkten. Z. Wahr. Verw. Geb. 2, 75–84 (1963)
Rényi, A., Sulanke, R.: Über die konvexe Hülle von n zufällig gewählten Punkten. II. Z. Wahr. Verw. Geb. 3, 138–147 (1963)
Schneider, R., Weil, W.: Stochastic and Integral Geometry. Springer, Berlin (2008)
Sommerville, D.: The relations connecting the angle sums and volume of a polytope in space of n dimensions. Proc. R. Soc. Lond. Ser. A 115, 103–119 (1927)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cowan, R. Recurrence Relationships for the Mean Number of Faces and Vertices for Random Convex Hulls. Discrete Comput Geom 43, 209–220 (2010). https://doi.org/10.1007/s00454-008-9122-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9122-6