Recent Results on Random Polytopes

Rolf Schneider

Bollettino dell'Unione Matematica Italiana (2008)

  • Volume: 1, Issue: 1, page 17-39
  • ISSN: 0392-4041

Abstract

top
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.

How to cite

top

Schneider, Rolf. "Recent Results on Random Polytopes." Bollettino dell'Unione Matematica Italiana 1.1 (2008): 17-39. <http://eudml.org/doc/290475>.

@article{Schneider2008,
abstract = {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.},
author = {Schneider, Rolf},
journal = {Bollettino dell'Unione Matematica Italiana},
language = {eng},
month = {2},
number = {1},
pages = {17-39},
publisher = {Unione Matematica Italiana},
title = {Recent Results on Random Polytopes},
url = {http://eudml.org/doc/290475},
volume = {1},
year = {2008},
}

TY - JOUR
AU - Schneider, Rolf
TI - Recent Results on Random Polytopes
JO - Bollettino dell'Unione Matematica Italiana
DA - 2008/2//
PB - Unione Matematica Italiana
VL - 1
IS - 1
SP - 17
EP - 39
AB - 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.
LA - eng
UR - http://eudml.org/doc/290475
ER -

References

top
  1. AFFENTRANGER, F. - SCHNEIDER, R., Random projections of regular simplices, Discrete Comput. Geom., 7 (1992), 219-226. Zbl0751.52002MR1149653DOI10.1007/BF02187839
  2. AVRAM, F. - BERTSIMAS, D., On central limit theorems in geometrical probability, Ann. Appl. Probab., 3 (1993), 1033-1046. Zbl0784.60015MR1241033
  3. BÁRÁNY, I., Random polytopes in smooth convex bodies, Mathematika, 39 (1982), 81-92. 
  4. BÁRÁNY, I., 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 Mathematics1892, pp. 77-118, Springer, Berlin (2007). MR2327289
  5. BÁRÁNY, I. - LARMAN, D. G., Convex bodies, economic cap coverings, random polytopes, Mathematika, 35 (1988), 274-291. Zbl0674.52003MR986636DOI10.1112/S0025579300015266
  6. BÁRÁNY, I. - REITZNER, M., Random polytopes, (submitted). MR2654675
  7. BÁRÁNY, I. - VU, V., Central limit theorems for Gaussian polytopes, Ann. Probab., 35 (2007), 1593-1621. Zbl1124.60014MR2330981DOI10.1214/009117906000000791
  8. BARYSHNIKOV, Y. N. - VITALE, R. A., Regular simplices and Gaussian samples, Discrete Comput. Geom., 11 (1994), 141-147. Zbl0795.52002MR1254086DOI10.1007/BF02574000
  9. BÖRÖCZKY JR, K.. - HENK, M., Random projections of regular polytopes, Arch. Math., 73 (1999), 465-473. MR1725183DOI10.1007/s000130050424
  10. BUCHTA, C., An identity relating moments of functionals of convex hulls, Discrete Comput. Geom., 33 (2005), 125-142. Zbl1065.52003MR2105754DOI10.1007/s00454-004-1109-3
  11. CABO, A. J. - GROENEBOOM, P., Limit theorems for functionals of convex hulls, Probab. Theory Rel. Fields, 100 (1994), 31-55. Zbl0808.60019MR1292189DOI10.1007/BF01204952
  12. DONOHO, D. L., Neighborly polytopes and sparse solutions of underdetermined linear equations, Technical Report, Department of Statistics, Stanford University (2004). 
  13. DONOHO, D. L., High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete Comput. Geom., 35 (2006), 617-652. Zbl1095.52500MR2225676DOI10.1007/s00454-005-1220-0
  14. DONOHO, D. L. - TANNER, J., Sparse nonnegative solutions of underdetermined linear equations by linear programming, Proc. Natl. Acad. Sci. USA, 102 (2005), no. 27, 9446-9451. Zbl1135.90368MR2168715DOI10.1073/pnas.0502269102
  15. DONOHO, D. L. - TANNER, J., Neighborliness of randomly projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA, 102 (2005), no. 27, 9452-9457. Zbl1135.60300MR2168716DOI10.1073/pnas.0502258102
  16. DONOHO, D. L. - TANNER, J., 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) Zbl1206.52010MR2449053DOI10.1090/S0894-0347-08-00600-0
  17. GOLDMAN, A., 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. Zbl0936.60009MR1675067DOI10.1214/aop/1022855880
  18. GROENEBOOM, P., Convex hulls of uniform samples from a convex polygon, Preprint (2006). Zbl1251.60011MR2977398DOI10.1239/aap/1339878714
  19. HUG, D. - MUNSONIUS, G. O. - REITZNER, M., Asymptotic mean values of Gaussian polytopes, Beiträge Algebra Geom., 45 (2004), 531-548. Zbl1082.52003MR2093024
  20. HUG, D. - REITZNER, M., Gaussian polytopes: variances and limit theorems, Adv. Appl. Prob. (SGSA), 37 (2005), 297-320. Zbl1089.52003MR2144555DOI10.1239/aap/1118858627
  21. HUG, D. - REITZNER, M. - SCHNEIDER, R., The limit shape of the zero cell in a stationary Poisson hyperplane tessellation, Ann. Probab., 32 (2004), 1140-1167. Zbl1050.60010MR2044676DOI10.1214/aop/1079021474
  22. HUG, D. - REITZNER, M. - SCHNEIDER, R., Large Poisson-Voronoi cells and Crofton cells, Adv. Appl. Prob. (SGSA), 36 (2004), 667-690. Zbl1069.60010MR2079908DOI10.1239/aap/1093962228
  23. HUG, D. - SCHNEIDER, R., Large cells in Poisson-Delaunay tessellations, Discrete Comput. Geom., 31 (2004), 503-514. Zbl1074.60009MR2053496DOI10.1007/s00454-003-0818-3
  24. HUG, D. - SCHNEIDER, R., Large typical cells in Poisson-Delaunay mosaics, Rev. Roumaine Math. Pures Appl., 50 (2005), 657-670. Zbl1113.60016MR2204143
  25. HUG, D. - SCHNEIDER, R., Asymptotic shapes of large cells in random tessellations, Geom. Funct. Anal., 17 (2007), 156-191. Zbl1114.60012MR2306655DOI10.1007/s00039-007-0592-0
  26. HUG, D. - SCHNEIDER, R., Typical cells in Poisson hyperplane tessellations, Discrete Comput. Geom., 38 (2007), 305-319. Zbl1140.60009MR2343310DOI10.1007/s00454-007-1340-9
  27. KOVALENKO, I. N., 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. MR1609157DOI10.1007/BF02733102
  28. KOVALENKO, I. N., 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. KOVALENKO, I. N., A simplified proof of a conjecture of D. G. Kendall concerning shapes of random polygons, J. Appl. Math. Stochastic Anal., 12 (1999), 301-310. Zbl0959.60007MR1736071DOI10.1155/S1048953399000283
  30. LINIAL, N. - NOVIK, I., How neighborly can a centrally symmetric polytope be?, Discrete Comput. Geom., 36 (2006), 273-281. Zbl1127.52011MR2252105DOI10.1007/s00454-006-1235-1
  31. MECKE, J. - OSBURG, I., On the shape of large Crofton parallelotopes, Math. Notae, 41 (2003), 149-157. Zbl1202.60024MR2049441
  32. MILES, R. E., 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. Zbl0829.60008MR1334821DOI10.2307/1427833
  33. REITZNER, M., Random polytopes and the Efron-Stein jackknife inequality, Ann. Probab., 31 (2003), 2136-2166. Zbl1058.60010MR2016615DOI10.1214/aop/1068646381
  34. REITZNER, M., Central limit theorems for random polytopes, Probab. Theory Relat. Fields, 133 (2005), 483-507. Zbl1081.60008MR2197111DOI10.1007/s00440-005-0441-8
  35. RÉNYI, A. - SULANKE, R., Über die konvexe Hulle von n zufällig gewählten Punkten, Z. Wahrscheinlichkeitsth. verw. Geb., 2 (1963), 75-84. Zbl0118.13701MR156262DOI10.1007/BF00535300
  36. RÉNYI, A. - SULANKE, R., Über die konvexe Hülle von n zufällig gewählten Punkten, II, Z. Wahrscheinlichkeitsth. verw. Geb., 3 (1964), 138-147. MR169139DOI10.1007/BF00535973
  37. RÉNYI, A. - SULANKE, R., Zufällige konvexe Polygone in einem Ringgebiet, Z. Wahrscheinlichkeitsth. verw. Geb., 9 (1968), 146-157. MR229272DOI10.1007/BF01851005
  38. RINOTT, Y., On normal approximation rates for certain sums of dependent random variables, J. Comput. Appl. Math., 55 (1994), 135-147. Zbl0821.60037MR1327369DOI10.1016/0377-0427(94)90016-7
  39. SCHNEIDER, R., Random approximation of convex sets, J. Microscopy, 151 (1988), 211-227. Zbl1256.52004
  40. SCHNEIDER, R., Convex Bodies - the Brunn-Minkowski Theory, Cambridge University Press, Cambridge (1993). Zbl0798.52001MR1216521DOI10.1017/CBO9780511526282
  41. SCHNEIDER, R., 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). MR1730165
  42. SCHNEIDER, R. - WEIL, W., Stochastische Geometrie, Teubner, Stuttgart (2000). MR1794753DOI10.1007/978-3-322-80106-7
  43. SCHÜTT, C., Random polytopes and affine surface area, Math. Nachr., 170 (1994), 227-249. MR1302377DOI10.1002/mana.19941700117
  44. SCHÜTT, C. - WERNER, E., 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). MR2083401DOI10.1007/978-3-540-36428-3_19
  45. STOYAN, D. - KENDALL, W. S. - MECKE, J., Stochastic Geometry and Its Applications, 2nd ed., Wiley, Chichester (1995). Zbl0838.60002MR895588
  46. SYLVESTER, J.J., Question 1491, Educational Times, London, April (1864). MR1472424DOI10.1098/rsnr.1997.0021
  47. VERSHIK, A. M. - SPORYSHEV, P. V., 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. Zbl0621.90046MR850459
  48. VERSHIK, A. M. - SPORYSHEV, P. V., Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem, Selecta Math. Soviet., 11 (1992), 181-201. Zbl0791.52011MR1166627
  49. VU, V., Sharp concentration of random polytopes, Geom. Funct. Anal., 15 (2005), 1284-1318. Zbl1094.52002MR2221249DOI10.1007/s00039-005-0541-8
  50. VU, V., Central limit theorems for random polytopes in a smooth convex set, Adv. Math., 207 (2006), 221-243. Zbl1111.52010MR2264072DOI10.1016/j.aim.2005.11.011
  51. WEIL, W. - WIEACKER, J. A., Stochastic geometry, in Handbook of Convex Geometry (P. M. Gruber - J. M. Wills, eds.), vol. B, pp. 1391-1438, North-Holland, Amsterdam (1993). MR1243013

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.