Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Random points and lattice points in convex bodies


Author: Imre Bárány
Journal: Bull. Amer. Math. Soc. 45 (2008), 339-365
MSC (2000): Primary 52A22, 52B20
DOI: https://doi.org/10.1090/S0273-0979-08-01210-X
Published electronically: April 25, 2008
MathSciNet review: 2402946
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Assume $ K \subset \mathbf{R}^d$ is a convex body and $ X$ is a (large) finite subset of $ K$. How many convex polytopes are there whose vertices belong to $ X$? Is there a typical shape of such polytopes? How well does the maximal such polytope (which is actually the convex hull of $ X$) approximate $ K$? We are interested in these questions mainly in two cases. The first is when $ X$ is a random sample of $ n$ uniform, independent points from $ K$. In this case motivation comes from Sylvester's famous four-point problem and from the theory of random polytopes. The second case is when $ X=K \cap \mathbf{Z}^d$ where $ \mathbf{Z}^d$ is the lattice of integer points in $ \mathbf{R}^d$ and the questions come from integer programming and geometry of numbers. Surprisingly (or not so surprisingly), the answers in the two cases are rather similar.


References [Enhancements On Off] (What's this?)

  • 1. Affentranger, F., Wieacker, J.A.: On the convex hull of uniform random points in a simple $ d$-polytope. Discrete Comp. Geom., 6 (1991), 291-305. MR 1098810 (92c:52004)
  • 2. Andrews, G.E.: A lower bound for the volumes of strictly convex bodies with many boundary points. Trans. Amer. Math. Soc., 106 (1993), 270-279. MR 0143105 (26:670)
  • 3. Arnold, V.I.: Statistics of integral convex polytopes. (in Russian) Funk. Anal. Pril., 14, 1-3 (1980). English translation: Funct. Anal. Appl., 14 (1980), 79-84. MR 575199 (81g:52011)
  • 4. Avram, F., Bertsimas, D.: On central limit theorems in geometrical probability. Ann. Appl. Probab., 3 (1993), 1033-1046. MR 1241033 (95d:60022)
  • 5. Baldi, P., Rinott, Y.: On normal approximations of distributions in terms of dependency graphs. Ann. Probab., 17 (1989), 1646-1650. MR 1048950 (91c:60024)
  • 6. Balog, A., Bárány, I.: On the convex hull of the integer points in a disk, in: Discrete and Computational Geometry (eds. J.E. Goodman, R. Pollack, and W. Steiger), DIMACS Series no. 6 (1991), 39-44. MR 1143287 (93b:11083)
  • 7. Balog, A., Deshouliers, J-M.: On some convex lattice polytopes. in: Number theory in progress, Vol. 2 (Zakopane-Kościelisko, 1997), 591-606, de Gruyter, Berlin, 1999. MR 1689533 (2000f:11083)
  • 8. Bárány, I.: Intrinsic volumes and $ f$-vectors of random polytopes. Math. Annalen, 285 (1989), 671-699. MR 1027765 (91c:52008)
  • 9. Bárány, I.: Random polytopes in smooth convex bodies. Mathematika, 39 (1992), 81-92. MR 1176473 (93k:52002)
  • 10. Bárány, I.: The limit shape of convex lattice polygons, Discrete Comp. Geom., 13 (1995), 270-295. MR 1318778 (95m:52037)
  • 11. Bárány, I.: Affine perimeter and limit shape, J. Reine Angew. Math., 484 (1997), 71-84. MR 1437299 (98a:52026)
  • 12. Bárány, I.: Sylvester's question: the probability that $ n$ points are in convex position. Annals of Prob., 27 (2000), 2020-2034. MR 1742899 (2001a:60010)
  • 13. Bárány, I.: A note on Sylvester's four-point problem. Studia Math. Hung., 38 (2001), 2020-2034. MR 1877770 (2002m:60020)
  • 14. Bárány, I., Buchta, Ch.: Random polytopes in a convex polytope, independence of shape, and concentration of vertices. Math. Annalen, 297 (1993), 467-497. MR 1245400 (95g:52005)
  • 15. Bárány, I., Dalla, L.: Few points to generate a random polytope, Mathematika, 44 (1997), 325-331. MR 1600549 (99b:52008)
  • 16. Bárány, I., Füredi, Z.: On the shape of the convex hull of random points, Prob. Theory Rel. Fields, 77 (1988), 231-240. MR 927239 (89g:60030)
  • 17. Bárány, I. Howe, R., Lovász, L.: On integer points in polyhedra: a lower bound. Combinatorica, 12 (1992), 135-142. MR 1179250 (93g:52012)
  • 18. Bárány, I., Larman, D.G.: Convex bodies, economic cap coverings, random polytopes. Mathematika, 35 (1988), 274-291. MR 986636 (90c:52020)
  • 19. Bárány, I., Larman, D.G.: The convex hull of the integer points in a large ball. Math. Annalen, 312 (1998), 167-181. MR 1645957 (99i:52014)
  • 20. Bárány, I., Matoušek, J.: The randomized integer hull. Discr. Comp. Geom., 33 (2005), 3-25. MR 2104706 (2006b:52003)
  • 21. Bárány, I., Pach, J.: On the number of convex lattice polygons, Combinatorics, Probability, and Computation, 1 (1992), 295-302. MR 1211319 (93m:52017)
  • 22. Bárány, I., Reitzner, M.: Central limit theorems for random polytopes in convex polytopes. manuscript (2007)
  • 23. Bárány, I., Rote, G., Steiger, W., Zhang, C.: A central limit theorem for random convex chains. Discrete Comp. Geom., 30 (2000), 35-50.
  • 24. Bárány, I., Vershik, A.M.: On the number of convex lattice polytopes. GAFA Journal, 12 (1992), 381-393. MR 1191566 (93k:52013)
  • 25. Bárány, I., Vu, H.V.: Central limit theorems for Gaussian polytopes. Annals of Prob., 35 (2007), 1593-1621. MR 2330981
  • 26. Blaschke, W.: Über affine Geometrie XI: L'osung des ``Vierpunktproblem'' von Sylvester aus der Theorie der geometrischen Wahrscheinlichkeiten. Leipziger Berichte, 69 (1917), 436-453.
  • 27. Blaschke, W.: Affine Differentialgeometrie. Springer, Berlin, (1923).
  • 28. Bräker, H., Hsing, T., Bingham, N.H.: On the Hausdorff distance between a convex set and an interior random convex hull. Adv. in Appl. Probab., 30 (1998), 295-316. MR 1642840 (99f:60020)
  • 29. Buchta, C.: On a conjecture of R.E. Miles about the convex hull of random points, Monatsh. Math., 102 (1986), 91-102. MR 861933 (88f:60016)
  • 30. Buchta, C.: An identity relating moments of functionals of convex hulls. Discrete Comput. Geom. 33 (2005), 125-142. MR 2105754 (2005j:60022)
  • 31. Cabo, A. J., Groeneboom, P.: Limit theorems for functionals of convex hulls. Probab. Theory Relat. Fields, 100 (1994), 31-55. MR 1292189 (95g:60017)
  • 32. Calka, P., Schreiber, T.: Large deviation probabilities for the number of vertices of random polytopes in the ball, Adv. in Appl. Probab., 38 (2006), 47-58. MR 2213963 (2007a:60011)
  • 33. Cook, W., Hartman, M., Kannan, R., McDiarmid, C.: On integer points in polyhedra. Combinatorica, 12 (1992), 27-37. MR 1167473 (93e:52025)
  • 34. Efron, B.: The convex hull of a random set of points. Biometrika, 52 (1965), 331-343. MR 0207004 (34:6820)
  • 35. Efron, B., Stein, C.: The jackknife estimate of variance. Ann. Statist., 9 (1981), 586-596. MR 615434 (82k:62074)
  • 36. Groemer, H.: On the mean value of the volume of a random polytope in a convex set. Archiv Math., 25 (1997), 86-90. MR 0341286 (49:6036)
  • 37. Groeneboom, P.: Limit theorems for convex hulls. Probab. Theory Relat. Fields, 79 (1988), 327-368. MR 959514 (89j:60024)
  • 38. Hostinsky, B.: Sur les probabilités géométriques. Publ. Fac. Sci. Univ. Brno (1925).
  • 39. Kingman, J. F. C.: Random secants of a convex body. J. Appl. Probab., 6 (1969), 660-672. MR 0254891 (40:8098)
  • 40. Hsing, T.: On the asymptotic distribution of the area outside a random convex hull in a disk. Ann. Appl. Probab., 4 (1994), 478-493. MR 1272736 (95d:60047)
  • 41. Kannan, R., Lovász, L.: Covering minima and lattice point free convex bodies. Annals of Math., 128 (1988), 577-622. MR 970611 (89i:52020)
  • 42. Khintchin, A.: A quantitative formulation of Kronecker's theory of approximation. (in Russian) Izv. Akad. Nauk SSSR, Ser. Mat., 12 (1948), 113-122. MR 0024925 (9:569d)
  • 43. Kim, J.H., Vu, V.H.: Concentration of multivariate polynomials and its applications. Combinatorica, 20 (2000), 417-434. MR 1774845 (2002b:05123)
  • 44. Konyagin, S.B., Sevastyanov, S.V.: Estimation of the number of vertices of a convex integral polyhedron in terms of its volume. (in Russian) Funk. Anal. Pril., 18 (1984), 13-15. English translation: Funct. Anal. Appl., 18 (1984), 11-13. MR 739085 (86g:52020)
  • 45. Küfer, K.-H.: On the approximation of the ball by random polytopes. Adv. Applied Prob., 26 (1994), 876-892. MR 1303867 (96j:60012)
  • 46. Miles, R. E., Isotropic random simplices. Adv. Appl. Prob., 3 (1971), 353-382. MR 0309164 (46:8274)
  • 47. Penrose, M.D., Yukich, J.E.: Normal approximation in geometric probability. Stein's method and applications, 37-58, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., 5, Singapore Univ. Press, Singapore, 2005. MR 2201885 (2007f:60015)
  • 48. Reisner, Sh., Schütt, C., Werner, E.: Dropping a vertex or a facet from a polytope. Forum Math., 13 (2001), 359-378. MR 1831090 (2002f:52003)
  • 49. Reitzner, M.: The combinatorial structure of random polytopes. Adv. Math., 191 (2005), 178-208. MR 2102847 (2005k:52015)
  • 50. Reitzner, M.: Random polytopes and the Efron-Stein jackknife inequality. Ann. Probab., 31 (2003), 2136-2166. MR 2016615 (2005b:60026)
  • 51. Reitzner, M.: Central limit theorems for random polytopes. Probab. Theory Relat. Fields, 133 (2005), 483-507. MR 2197111 (2007d:52005)
  • 52. Rinott, Y.: On normal approximation rates for certain sums of dependent random variables. J. Comput. Appl. Math., 55 (1994), 135-143. MR 1327369 (96m:60057)
  • 53. Rényi, A., Sulanke, R.: Über die konvexe Hülle von $ n$ zufällig gewählten Punkten. Z. Wahrsch. Verw. Geb., 2 (1963), 75-84. MR 0156262 (27:6190)
  • 54. Santaló, L.A.: Integral geometry and geometric probability. Addison-Wiley, Reading MA (1976). MR 0433364 (55:6340)
  • 55. Schmidt, W.: Integral points on surfaces and curves. Monatshefte Math., 99 (1985), 45-82. MR 778171 (86d:11081)
  • 56. Schneider, R., Wieacker, J.A.: Random polytopes in a convex body. Z. Wahrsch. Verw. Gebiete, 52 (1980), 69-73. MR 568260 (81f:52008)
  • 57. Schütt, C.: Random polytopes and affine surface area. Math. Nachr., 170 (1994), 227-249. MR 1302377 (95k:52007)
  • 58. Sinai, Ya. G.: Probabilistic approach to analyse the statistics of convex polygonal curves. (in Russian) Funk. Anal. Appl. 28, 41-48 (1994). English translation: Funct. Anal. Appl., 28 (1994), 108-113. MR 1283251 (95f:52015)
  • 59. Sulanke, R.: Letter to the author, 2004
  • 60. Sylvester, J.J.: Question 1491. Educational Times, London, April (1864).
  • 61. Sylvester, J.J.: Report of the British Association, 35 (1865), 8-9.
  • 62. Valtr, P.: The probability that $ n$ random points in a triangle are in convex position. Combinatorica, 16 (1996), 567-574. MR 1433643 (97k:60030)
  • 63. Vershik, A.M.: The limit shape for convex lattice polygons and related topics. (in Russian) Funk. Anal. Appl., 28 (1994), 16-25. English translation: Funct. Anal. Appl., 28 (1994), 13-20. MR 1275724 (95i:52010)
  • 64. Vershik A.M., Zeitouni, O.: Large deviation in the geometry of convex lattice polygons. Israel J. Math., 109 (1999), 13-27. MR 1679585 (2000i:52014)
  • 65. Vu, V.H.: On the concentration of multivariate polynomials with small expectations. Random Struct. Alg., 16 (2000), 344-363. MR 1761580 (2001g:60060)
  • 66. Vu, V.H.: Concentration of non-Lipschitz functions and applications. Random Struct. Alg., 20 (2002), 262-316. MR 1900610 (2003c:60053)
  • 67. Vu, V.H.: Sharp concentration of random polytopes. Geom. Funct. Anal., 15 (2005), 1284-1318. MR 2221249 (2007f:52012)
  • 68. Vu, V.H.: Central limit theorems for random polytopes in a smooth convex set. Adv. Math., 207 (2006), 221-243. MR 2264072 (2007k:60039)
  • 69. W. Weil, J.A. Wieacker: Stochastic geometry. In: Gruber, P.M., Wills, J. (eds.) Handbook of convex geometry, North-Holland, Amsterdam, 1391-1438 (1993). MR 1243013 (95a:60014)
  • 70. Wieacker, J.A.: Einige Probleme der polyedrische approximation. Diplomarbeit, Albert-Ludwigs-Universität, Freiburg im Breisgau, (1978)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 52A22, 52B20

Retrieve articles in all journals with MSC (2000): 52A22, 52B20


Additional Information

Imre Bárány
Affiliation: Rényi Institute of Mathematics, Hungarian Academy of Sciences, P. O. Box 127, 1364 Budapest, Hungary; and Department of Mathematics, University College London, Gower Street, London WC1E 6BT, England
Email: barany@renyi.hu, barany@math.ucl.ac.uk

DOI: https://doi.org/10.1090/S0273-0979-08-01210-X
Received by editor(s): November 2, 2007
Published electronically: April 25, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society