This is a survey over recent asymptotic results on random polytopes in d-dimensional Euclidean space. Three ways of generating a random polytope are considered: convex hulls of finitely many random points, projections of a fixed high-dimensional polytope into a random d-dimensional subspace, intersections of random closed halfspaces. The type of problems for which asymptotic results are described is different in each case.
@article{BUMI_2008_9_1_1_17_0,
author = {Rolf Schneider},
title = {Recent Results on Random Polytopes},
journal = {Bollettino dell'Unione Matematica Italiana},
volume = {1},
year = {2008},
pages = {17-39},
zbl = {1206.52011},
mrnumber = {2387995},
language = {en},
url = {http://dml.mathdoc.fr/item/BUMI_2008_9_1_1_17_0}
}
Schneider, Rolf. Recent Results on Random Polytopes. Bollettino dell'Unione Matematica Italiana, Tome 1 (2008) pp. 17-39. http://gdmltest.u-ga.fr/item/BUMI_2008_9_1_1_17_0/
[1] - , Random projections of regular simplices, Discrete Comput. Geom., 7 (1992), 219-226. | MR 1149653 | Zbl 0751.52002
[2] - , On central limit theorems in geometrical probability, Ann. Appl. Probab., 3 (1993), 1033-1046. | MR 1241033 | Zbl 0784.60015
[3] , Random polytopes in smooth convex bodies, Mathematika, 39 (1982), 81-92.
[4] , Random polytopes, convex bodies, and approximation, in - - - , Stochastic Geometry, C.I.M.E. Summer School, Martina Franca, Italy, 2004 (, ed.), Lecture Notes in Mathematics 1892, pp. 77-118, Springer, Berlin (2007). | MR 2327289
[5] - , Convex bodies, economic cap coverings, random polytopes, Mathematika, 35 (1988), 274-291. | MR 986636 | Zbl 0674.52003
[6] - , Random polytopes, (submitted). | MR 2654675
[7] - , Central limit theorems for Gaussian polytopes, Ann. Probab., 35 (2007), 1593-1621. | MR 2330981 | Zbl 1124.60014
[8] - , Regular simplices and Gaussian samples, Discrete Comput. Geom., 11 (1994), 141-147. | MR 1254086 | Zbl 0795.52002
[9] . - , Random projections of regular polytopes, Arch. Math., 73 (1999), 465-473. | MR 1725183
[10] , An identity relating moments of functionals of convex hulls, Discrete Comput. Geom., 33 (2005), 125-142. | MR 2105754 | Zbl 1065.52003
[11] - , Limit theorems for functionals of convex hulls, Probab. Theory Rel. Fields, 100 (1994), 31-55. | MR 1292189 | Zbl 0808.60019
[12] , Neighborly polytopes and sparse solutions of underdetermined linear equations, Technical Report, Department of Statistics, Stanford University (2004).
[13] , High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete Comput. Geom., 35 (2006), 617-652. | MR 2225676 | Zbl 1095.52500
[14] - , Sparse nonnegative solutions of underdetermined linear equations by linear programming, Proc. Natl. Acad. Sci. USA, 102 (2005), no. 27, 9446-9451. | MR 2168715 | Zbl 1135.90368
[15] - , Neighborliness of randomly projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA, 102 (2005), no. 27, 9452-9457. | MR 2168716 | Zbl 1135.60300
[16] - , Counting faces of randomly-projected polytopes when the projection radically lowers dimension, Technical Report No. 2006-11, Dept. of Statistics, Stanford University, J. Amer. Math. Soc. (to appear) | MR 2449053 | Zbl 1206.52010
[17] , Sur une conjecture de D.G. Kendall concernant la cellule de Crofton du plan et sur sa contrepartie brownienne, Ann. Probab., 26 (1998), 1727-1750. | MR 1675067 | Zbl 0936.60009
[18] , Convex hulls of uniform samples from a convex polygon, Preprint (2006). | MR 2977398 | Zbl 1251.60011
[19] - - , Asymptotic mean values of Gaussian polytopes, Beiträge Algebra Geom., 45 (2004), 531-548. | MR 2093024 | Zbl 1082.52003
[20] - , Gaussian polytopes: variances and limit theorems, Adv. Appl. Prob. (SGSA), 37 (2005), 297-320. | MR 2144555 | Zbl 1089.52003
[21] - - , The limit shape of the zero cell in a stationary Poisson hyperplane tessellation, Ann. Probab., 32 (2004), 1140-1167. | MR 2044676 | Zbl 1050.60010
[22] - - , Large Poisson-Voronoi cells and Crofton cells, Adv. Appl. Prob. (SGSA), 36 (2004), 667-690. | MR 2079908 | Zbl 1069.60010
[23] - , Large cells in Poisson-Delaunay tessellations, Discrete Comput. Geom., 31 (2004), 503-514. | MR 2053496 | Zbl 1074.60009
[24] - , Large typical cells in Poisson-Delaunay mosaics, Rev. Roumaine Math. Pures Appl., 50 (2005), 657-670. | MR 2204143 | Zbl 1113.60016
[25] - , Asymptotic shapes of large cells in random tessellations, Geom. Funct. Anal., 17 (2007), 156-191. | MR 2306655 | Zbl 1114.60012
[26] - , Typical cells in Poisson hyperplane tessellations, Discrete Comput. Geom., 38 (2007), 305-319. | MR 2343310 | Zbl 1140.60009
[27] , A proof of a conjecture of David Kendall on the shape of random polygons of large area (Russian), Kibernet. Sistem. Anal. 1997, 3-10, 187, Engl. transl.: Cybernet. Systems Anal., 33 (1997), 461-467. | MR 1609157
[28] , An extension of a conjecture of D.G. Kendall concerning shapes of random polygons to Poisson Voronoï cells, in Voronoï's Impact on Modern Science ( et al., eds.), Book I. Transl. from the Ukrainian, Kyiv: Institute of Mathematics. Proc. Inst. Math. Natl. Acad. Sci. Ukr., Math. Appl., 212 (1998), 266- 274.
[29] , A simplified proof of a conjecture of D. G. Kendall concerning shapes of random polygons, J. Appl. Math. Stochastic Anal., 12 (1999), 301-310. | MR 1736071 | Zbl 0959.60007
[30] - , How neighborly can a centrally symmetric polytope be?, Discrete Comput. Geom., 36 (2006), 273-281. | MR 2252105 | Zbl 1127.52011
[31] - , On the shape of large Crofton parallelotopes, Math. Notae, 41 (2003), 149-157. | MR 2049441 | Zbl 1202.60024
[32] , A heuristic proof of a long-standing conjecture of D. G. Kendall concerning the shapes of certain large random polygons, Adv. Appl. Prob. (SGSA), 27 (1995), 397-417. | MR 1334821 | Zbl 0829.60008
[33] , Random polytopes and the Efron-Stein jackknife inequality, Ann. Probab., 31 (2003), 2136-2166. | MR 2016615 | Zbl 1058.60010
[34] , Central limit theorems for random polytopes, Probab. Theory Relat. Fields, 133 (2005), 483-507. | MR 2197111 | Zbl 1081.60008
[35] - , Über die konvexe Hulle von n zufällig gewählten Punkten, Z. Wahrscheinlichkeitsth. verw. Geb., 2 (1963), 75-84. | MR 156262 | Zbl 0118.13701
[36] - , Über die konvexe Hülle von n zufällig gewählten Punkten, II, Z. Wahrscheinlichkeitsth. verw. Geb., 3 (1964), 138-147. | MR 169139
[37] - , Zufällige konvexe Polygone in einem Ringgebiet, Z. Wahrscheinlichkeitsth. verw. Geb., 9 (1968), 146-157. | MR 229272
[38] , On normal approximation rates for certain sums of dependent random variables, J. Comput. Appl. Math., 55 (1994), 135-147. | MR 1327369 | Zbl 0821.60037
[39] , Random approximation of convex sets, J. Microscopy, 151 (1988), 211-227. | Zbl 1256.52004
[40] , Convex Bodies - the Brunn-Minkowski Theory, Cambridge University Press, Cambridge (1993). | MR 1216521 | Zbl 0798.52001
[41] , Discrete aspects of stochastic geometry, in Handbook of Discrete and Computational Geometry ( - , eds.), 2nd ed., pp. 255-278, CRC Press, Boca Raton (2004). | MR 1730165
[42] - , Stochastische Geometrie, Teubner, Stuttgart (2000). | MR 1794753
[43] , Random polytopes and affine surface area, Math. Nachr., 170 (1994), 227-249. | MR 1302377
[44] - , Polytopes with vertices chosen randomly from the boundary of a convex body, Israel Seminar 2001-2002 (, , eds.), pp. 241-422, Lecture Notes in Math., vol. 1807, Springer, New York (2003). | MR 2083401
[45] - - , Stochastic Geometry and Its Applications, 2nd ed., Wiley, Chichester (1995). | MR 895588 | Zbl 0838.60002
[46] , Question 1491, Educational Times, London, April (1864). | MR 1472424
[47] - , An asymptotic estimate of the average number of steps of the parametric simplex method, U.S.S.R. Comput. Math. and Math. Phys., 26 (1986), 104-113. | MR 850459 | Zbl 0621.90046
[48] - , Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem, Selecta Math. Soviet., 11 (1992), 181-201. | MR 1166627 | Zbl 0791.52011
[49] , Sharp concentration of random polytopes, Geom. Funct. Anal., 15 (2005), 1284-1318. | MR 2221249 | Zbl 1094.52002
[50] , Central limit theorems for random polytopes in a smooth convex set, Adv. Math., 207 (2006), 221-243. | MR 2264072 | Zbl 1111.52010
[51] - , Stochastic geometry, in Handbook of Convex Geometry ( - , eds.), vol. B, pp. 1391-1438, North-Holland, Amsterdam (1993). | MR 1243013