Schneider: Recent Results on Random Polytopes

Schneider, Rolf:
Recent Results on Random Polytopes
Bollettino dell'Unione Matematica Italiana Serie 9 1 (2008), fasc. n.1, p. 17-39, (English)
pdf (470 Kb), djvu (225 Kb). | MR 2387995 | Zbl 1206.52011

Sunto

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.

Referenze Bibliografiche

[1] F. AFFENTRANGER - R. SCHNEIDER, Random projections of regular simplices, Discrete Comput. Geom., 7 (1992), 219-226. | fulltext EuDML | fulltext (doi) | MR 1149653 | Zbl 0751.52002

[2] F. AVRAM - D. BERTSIMAS, On central limit theorems in geometrical probability, Ann. Appl. Probab., 3 (1993), 1033-1046. | MR 1241033 | Zbl 0784.60015

[3] I. BÁRÁNY, Random polytopes in smooth convex bodies, Mathematika, 39 (1982), 81-92.

[4] I. BÁRÁNY, Random polytopes, convex bodies, and approximation, in A. J. Baddeley - I. Bárány - R. Schneider - W. Weil, Stochastic Geometry, C.I.M.E. Summer School, Martina Franca, Italy, 2004 (W. Weil, ed.), Lecture Notes in Mathematics 1892, pp. 77-118, Springer, Berlin (2007). | MR 2327289

[5] I. BÁRÁNY - D. G. LARMAN, Convex bodies, economic cap coverings, random polytopes, Mathematika, 35 (1988), 274-291. | fulltext (doi) | MR 986636 | Zbl 0674.52003

[6] I. BÁRÁNY - M. REITZNER, Random polytopes, (submitted). | MR 2654675

[7] I. BÁRÁNY - V. VU, Central limit theorems for Gaussian polytopes, Ann. Probab., 35 (2007), 1593-1621. | fulltext (doi) | MR 2330981 | Zbl 1124.60014

[8] Y. N. BARYSHNIKOV - R. A. VITALE, Regular simplices and Gaussian samples, Discrete Comput. Geom., 11 (1994), 141-147. | fulltext EuDML | fulltext (doi) | MR 1254086 | Zbl 0795.52002

[9] K. BÖRÖCZKY JR. - M. HENK, Random projections of regular polytopes, Arch. Math., 73 (1999), 465-473. | fulltext (doi) | MR 1725183

[10] C. BUCHTA, An identity relating moments of functionals of convex hulls, Discrete Comput. Geom., 33 (2005), 125-142. | fulltext (doi) | MR 2105754 | Zbl 1065.52003

[11] A. J. CABO - P. GROENEBOOM, Limit theorems for functionals of convex hulls, Probab. Theory Rel. Fields, 100 (1994), 31-55. | fulltext (doi) | MR 1292189 | Zbl 0808.60019

[12] D. L. DONOHO, Neighborly polytopes and sparse solutions of underdetermined linear equations, Technical Report, Department of Statistics, Stanford University (2004).

[13] D. L. DONOHO, High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete Comput. Geom., 35 (2006), 617-652. | fulltext (doi) | MR 2225676 | Zbl 1095.52500

[14] D. L. DONOHO - J. TANNER, Sparse nonnegative solutions of underdetermined linear equations by linear programming, Proc. Natl. Acad. Sci. USA, 102 (2005), no. 27, 9446-9451. | fulltext (doi) | MR 2168715 | Zbl 1135.90368

[15] D. L. DONOHO - J. TANNER, Neighborliness of randomly projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA, 102 (2005), no. 27, 9452-9457. | fulltext (doi) | MR 2168716 | Zbl 1135.60300

[16] D. L. DONOHO - J. TANNER, 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) | fulltext (doi) | MR 2449053 | Zbl 1206.52010

[17] A. GOLDMAN, 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. | fulltext (doi) | MR 1675067 | Zbl 0936.60009

[18] P. GROENEBOOM, Convex hulls of uniform samples from a convex polygon, Preprint (2006). | fulltext (doi) | MR 2977398 | Zbl 1251.60011

[19] D. HUG - G. O. MUNSONIUS - M. REITZNER, Asymptotic mean values of Gaussian polytopes, Beiträge Algebra Geom., 45 (2004), 531-548. | fulltext EuDML | MR 2093024 | Zbl 1082.52003

[20] D. HUG - M. REITZNER, Gaussian polytopes: variances and limit theorems, Adv. Appl. Prob. (SGSA), 37 (2005), 297-320. | fulltext (doi) | MR 2144555 | Zbl 1089.52003

[21] D. HUG - M. REITZNER - R. SCHNEIDER, The limit shape of the zero cell in a stationary Poisson hyperplane tessellation, Ann. Probab., 32 (2004), 1140-1167. | fulltext (doi) | MR 2044676 | Zbl 1050.60010

[22] D. HUG - M. REITZNER - R. SCHNEIDER, Large Poisson-Voronoi cells and Crofton cells, Adv. Appl. Prob. (SGSA), 36 (2004), 667-690. | fulltext (doi) | MR 2079908 | Zbl 1069.60010

[23] D. HUG - R. SCHNEIDER, Large cells in Poisson-Delaunay tessellations, Discrete Comput. Geom., 31 (2004), 503-514. | fulltext (doi) | MR 2053496 | Zbl 1074.60009

[24] D. HUG - R. SCHNEIDER, Large typical cells in Poisson-Delaunay mosaics, Rev. Roumaine Math. Pures Appl., 50 (2005), 657-670. | MR 2204143 | Zbl 1113.60016

[25] D. HUG - R. SCHNEIDER, Asymptotic shapes of large cells in random tessellations, Geom. Funct. Anal., 17 (2007), 156-191. | fulltext (doi) | MR 2306655 | Zbl 1114.60012

[26] D. HUG - R. SCHNEIDER, Typical cells in Poisson hyperplane tessellations, Discrete Comput. Geom., 38 (2007), 305-319. | fulltext (doi) | MR 2343310 | Zbl 1140.60009

[27] I. N. KOVALENKO, 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. | fulltext (doi) | MR 1609157

[28] I. N. KOVALENKO, 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 (Engel, P. 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] I. N. KOVALENKO, A simplified proof of a conjecture of D. G. Kendall concerning shapes of random polygons, J. Appl. Math. Stochastic Anal., 12 (1999), 301-310. | fulltext EuDML | fulltext (doi) | MR 1736071 | Zbl 0959.60007

[30] N. LINIAL - I. NOVIK, How neighborly can a centrally symmetric polytope be?, Discrete Comput. Geom., 36 (2006), 273-281. | fulltext (doi) | MR 2252105 | Zbl 1127.52011

[31] J. MECKE - I. OSBURG, On the shape of large Crofton parallelotopes, Math. Notae, 41 (2003), 149-157. | MR 2049441 | Zbl 1202.60024

[32] R. E. MILES, 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. | fulltext (doi) | MR 1334821 | Zbl 0829.60008

[33] M. REITZNER, Random polytopes and the Efron-Stein jackknife inequality, Ann. Probab., 31 (2003), 2136-2166. | fulltext (doi) | MR 2016615 | Zbl 1058.60010

[34] M. REITZNER, Central limit theorems for random polytopes, Probab. Theory Relat. Fields, 133 (2005), 483-507. | fulltext (doi) | MR 2197111 | Zbl 1081.60008

[35] A. RÉNYI - R. SULANKE, Über die konvexe Hulle von n zufällig gewählten Punkten, Z. Wahrscheinlichkeitsth. verw. Geb., 2 (1963), 75-84. | fulltext (doi) | MR 156262 | Zbl 0118.13701

[36] A. RÉNYI - R. SULANKE, Über die konvexe Hülle von n zufällig gewählten Punkten, II, Z. Wahrscheinlichkeitsth. verw. Geb., 3 (1964), 138-147. | fulltext (doi) | MR 169139

[37] A. RÉNYI - R. SULANKE, Zufällige konvexe Polygone in einem Ringgebiet, Z. Wahrscheinlichkeitsth. verw. Geb., 9 (1968), 146-157. | fulltext (doi) | MR 229272

[38] Y. RINOTT, On normal approximation rates for certain sums of dependent random variables, J. Comput. Appl. Math., 55 (1994), 135-147. | fulltext (doi) | MR 1327369 | Zbl 0821.60037

[39] R. SCHNEIDER, Random approximation of convex sets, J. Microscopy, 151 (1988), 211-227. | Zbl 1256.52004

[40] R. SCHNEIDER, Convex Bodies - the Brunn-Minkowski Theory, Cambridge University Press, Cambridge (1993). | fulltext (doi) | MR 1216521 | Zbl 0798.52001

[41] R. SCHNEIDER, Discrete aspects of stochastic geometry, in Handbook of Discrete and Computational Geometry (J. E. Goodman - J. O'Rourke, eds.), 2nd ed., pp. 255-278, CRC Press, Boca Raton (2004). | MR 1730165

[42] R. SCHNEIDER - W. WEIL, Stochastische Geometrie, Teubner, Stuttgart (2000). | fulltext (doi) | MR 1794753

[43] C. SCHÜTT, Random polytopes and affine surface area, Math. Nachr., 170 (1994), 227-249. | fulltext (doi) | MR 1302377

[44] C. SCHÜTT - E. WERNER, Polytopes with vertices chosen randomly from the boundary of a convex body, Israel Seminar 2001-2002 (V. D. Milman, G. Schechtman, eds.), pp. 241-422, Lecture Notes in Math., vol. 1807, Springer, New York (2003). | fulltext (doi) | MR 2083401

[45] D. STOYAN - W. S. KENDALL - J. MECKE, Stochastic Geometry and Its Applications, 2nd ed., Wiley, Chichester (1995). | MR 895588 | Zbl 0838.60002

[46] J.J. SYLVESTER, Question 1491, Educational Times, London, April (1864). | fulltext (doi) | MR 1472424

[47] A. M. VERSHIK - P. V. SPORYSHEV, 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] A. M. VERSHIK - P. V. SPORYSHEV, 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] V. VU, Sharp concentration of random polytopes, Geom. Funct. Anal., 15 (2005), 1284-1318. | fulltext (doi) | MR 2221249 | Zbl 1094.52002

[50] V. VU, Central limit theorems for random polytopes in a smooth convex set, Adv. Math., 207 (2006), 221-243. | fulltext (doi) | MR 2264072 | Zbl 1111.52010

[51] W. WEIL - J. A. WIEACKER, Stochastic geometry, in Handbook of Convex Geometry (P. M. Gruber - J. M. Wills, eds.), vol. B, pp. 1391-1438, North-Holland, Amsterdam (1993). | MR 1243013

bdim: Biblioteca Digitale Italiana di Matematica

Un progetto SIMAI e UMI

Referenza completa

Sunto

Referenze Bibliografiche