Geodesic
Recent Results on Random Polytopes
Bollettino della Unione matematica italiana, Série 9, Tome 1 (2008) no. 1, pp. 17-39.

Voir la notice de l'article provenant de la source Biblioteca Digitale Italiana di Matematica

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_a1,
     author = {Schneider, Rolf},
     title = {Recent {Results} on {Random} {Polytopes}},
     journal = {Bollettino della Unione matematica italiana},
     pages = {17--39},
     publisher = {mathdoc},
     volume = {Ser. 9, 1},
     number = {1},
     year = {2008},
     zbl = {1206.52011},
     mrnumber = {2387995},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BUMI_2008_9_1_1_a1/}
}
TY  - JOUR
AU  - Schneider, Rolf
TI  - Recent Results on Random Polytopes
JO  - Bollettino della Unione matematica italiana
PY  - 2008
SP  - 17
EP  - 39
VL  - 1
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BUMI_2008_9_1_1_a1/
LA  - en
ID  - BUMI_2008_9_1_1_a1
ER  - 
%0 Journal Article
%A Schneider, Rolf
%T Recent Results on Random Polytopes
%J Bollettino della Unione matematica italiana
%D 2008
%P 17-39
%V 1
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BUMI_2008_9_1_1_a1/
%G en
%F BUMI_2008_9_1_1_a1
Schneider, Rolf. Recent Results on Random Polytopes. Bollettino della Unione matematica italiana, Série 9, Tome 1 (2008) no. 1, pp. 17-39. http://geodesic.mathdoc.fr/item/BUMI_2008_9_1_1_a1/

[1] F. Affentranger - R. Schneider, Random projections of regular simplices, Discrete Comput. Geom., 7 (1992), 219-226. | fulltext EuDML | DOI | MR | Zbl

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

[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

[5] I. Bárány - D. G. Larman, Convex bodies, economic cap coverings, random polytopes, Mathematika, 35 (1988), 274-291. | DOI | MR | Zbl

[6] I. Bárány - M. Reitzner, Random polytopes, (submitted). | MR

[7] I. Bárány - V. Vu, Central limit theorems for Gaussian polytopes, Ann. Probab., 35 (2007), 1593-1621. | DOI | MR | Zbl

[8] Y. N. Baryshnikov - R. A. Vitale, Regular simplices and Gaussian samples, Discrete Comput. Geom., 11 (1994), 141-147. | fulltext EuDML | DOI | MR | Zbl

[9] K. Böröczky Jr. - M. Henk, Random projections of regular polytopes, Arch. Math., 73 (1999), 465-473. | DOI | MR

[10] C. Buchta, An identity relating moments of functionals of convex hulls, Discrete Comput. Geom., 33 (2005), 125-142. | DOI | MR | Zbl

[11] A. J. Cabo - P. Groeneboom, Limit theorems for functionals of convex hulls, Probab. Theory Rel. Fields, 100 (1994), 31-55. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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) | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[18] P. Groeneboom, Convex hulls of uniform samples from a convex polygon, Preprint (2006). | DOI | MR | Zbl

[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 | Zbl

[20] D. Hug - M. Reitzner, Gaussian polytopes: variances and limit theorems, Adv. Appl. Prob. (SGSA), 37 (2005), 297-320. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[22] D. Hug - M. Reitzner - R. Schneider, Large Poisson-Voronoi cells and Crofton cells, Adv. Appl. Prob. (SGSA), 36 (2004), 667-690. | DOI | MR | Zbl

[23] D. Hug - R. Schneider, Large cells in Poisson-Delaunay tessellations, Discrete Comput. Geom., 31 (2004), 503-514. | DOI | MR | Zbl

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

[25] D. Hug - R. Schneider, Asymptotic shapes of large cells in random tessellations, Geom. Funct. Anal., 17 (2007), 156-191. | DOI | MR | Zbl

[26] D. Hug - R. Schneider, Typical cells in Poisson hyperplane tessellations, Discrete Comput. Geom., 38 (2007), 305-319. | DOI | MR | Zbl

[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. | DOI | MR

[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 | DOI | MR | Zbl

[30] N. Linial - I. Novik, How neighborly can a centrally symmetric polytope be?, Discrete Comput. Geom., 36 (2006), 273-281. | DOI | MR | Zbl

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

[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. | DOI | MR | Zbl

[33] M. Reitzner, Random polytopes and the Efron-Stein jackknife inequality, Ann. Probab., 31 (2003), 2136-2166. | DOI | MR | Zbl

[34] M. Reitzner, Central limit theorems for random polytopes, Probab. Theory Relat. Fields, 133 (2005), 483-507. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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. | DOI | MR

[37] A. Rényi - R. Sulanke, Zufällige konvexe Polygone in einem Ringgebiet, Z. Wahrscheinlichkeitsth. verw. Geb., 9 (1968), 146-157. | DOI | MR

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

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

[40] R. Schneider, Convex Bodies - the Brunn-Minkowski Theory, Cambridge University Press, Cambridge (1993). | DOI | MR | Zbl

[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

[42] R. Schneider - W. Weil, Stochastische Geometrie, Teubner, Stuttgart (2000). | DOI | MR

[43] C. Schütt, Random polytopes and affine surface area, Math. Nachr., 170 (1994), 227-249. | DOI | MR

[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). | DOI | MR

[45] D. Stoyan - W. S. Kendall - J. Mecke, Stochastic Geometry and Its Applications, 2nd ed., Wiley, Chichester (1995). | MR | Zbl

[46] J.J. Sylvester, Question 1491, Educational Times, London, April (1864). | DOI | MR

[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 | Zbl

[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 | Zbl

[49] V. Vu, Sharp concentration of random polytopes, Geom. Funct. Anal., 15 (2005), 1284-1318. | DOI | MR | Zbl

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

[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