Random points and lattice points in convex bodies
HTML articles powered by AMS MathViewer
- by Imre Bárány PDF
- Bull. Amer. Math. Soc. 45 (2008), 339-365 Request permission
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
- Fernando Affentranger and John A. Wieacker, On the convex hull of uniform random points in a simple $d$-polytope, Discrete Comput. Geom. 6 (1991), no. 4, 291–305. MR 1098810, DOI 10.1007/BF02574691
- George E. Andrews, A lower bound for the volume of strictly convex bodies with many boundary lattice points, Trans. Amer. Math. Soc. 106 (1963), 270–279. MR 143105, DOI 10.1090/S0002-9947-1963-0143105-7
- V. I. Arnol′d, Statistics of integral convex polygons, Funktsional. Anal. i Prilozhen. 14 (1980), no. 2, 1–3 (Russian). MR 575199
- Florin Avram and Dimitris Bertsimas, On central limit theorems in geometrical probability, Ann. Appl. Probab. 3 (1993), no. 4, 1033–1046. MR 1241033
- Pierre Baldi and Yosef Rinott, On normal approximations of distributions in terms of dependency graphs, Ann. Probab. 17 (1989), no. 4, 1646–1650. MR 1048950
- Antal Balog and Imre Bárány, On the convex hull of the integer points in a disc, Discrete and computational geometry (New Brunswick, NJ, 1989/1990) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 6, Amer. Math. Soc., Providence, RI, 1991, pp. 39–44. MR 1143287, DOI 10.1090/dimacs/006/02
- Antal Balog and Jean-Marc Deshouillers, On some convex lattice polytopes, Number theory in progress, Vol. 2 (Zakopane-Kościelisko, 1997) de Gruyter, Berlin, 1999, pp. 591–606. MR 1689533
- Imre Bárány, Intrinsic volumes and $f$-vectors of random polytopes, Math. Ann. 285 (1989), no. 4, 671–699. MR 1027765, DOI 10.1007/BF01452053
- Imre Bárány, Random polytopes in smooth convex bodies, Mathematika 39 (1992), no. 1, 81–92. MR 1176473, DOI 10.1112/S0025579300006872
- I. Bárány, The limit shape of convex lattice polygons, Discrete Comput. Geom. 13 (1995), no. 3-4, 279–295. MR 1318778, DOI 10.1007/BF02574045
- Imre Bárány, Affine perimeter and limit shape, J. Reine Angew. Math. 484 (1997), 71–84. MR 1437299, DOI 10.1515/crll.1997.484.71
- Imre Bárány, Sylvester’s question: the probability that $n$ points are in convex position, Ann. Probab. 27 (1999), no. 4, 2020–2034. MR 1742899, DOI 10.1214/aop/1022677559
- I. Bárány, A note on Sylvester’s four-point problem, Studia Sci. Math. Hungar. 38 (2001), 73–77. MR 1877770, DOI 10.1556/SScMath.38.2001.1-4.5
- Imre Bárány and Christian Buchta, Random polytopes in a convex polytope, independence of shape, and concentration of vertices, Math. Ann. 297 (1993), no. 3, 467–497. MR 1245400, DOI 10.1007/BF01459511
- Imre Bárány and Leoni Dalla, Few points to generate a random polytope, Mathematika 44 (1997), no. 2, 325–331. MR 1600549, DOI 10.1112/S0025579300012638
- Imre Bárány and Zoltán Füredi, On the shape of the convex hull of random points, Probab. Theory Related Fields 77 (1988), no. 2, 231–240. MR 927239, DOI 10.1007/BF00334039
- Imre Bárány, Roger Howe, and László Lovász, On integer points in polyhedra: a lower bound, Combinatorica 12 (1992), no. 2, 135–142. MR 1179250, DOI 10.1007/BF01204716
- I. Bárány and D. G. Larman, Convex bodies, economic cap coverings, random polytopes, Mathematika 35 (1988), no. 2, 274–291. MR 986636, DOI 10.1112/S0025579300015266
- Imre Bárány and David G. Larman, The convex hull of the integer points in a large ball, Math. Ann. 312 (1998), no. 1, 167–181. MR 1645957, DOI 10.1007/s002080050217
- Imre Bárány and Jiří Matoušek, The randomized integer convex hull, Discrete Comput. Geom. 33 (2005), no. 1, 3–25. MR 2104706, DOI 10.1007/s00454-003-0836-1
- Imre Bárány and János Pach, On the number of convex lattice polygons, Combin. Probab. Comput. 1 (1992), no. 4, 295–302. MR 1211319, DOI 10.1017/S0963548300000341 br Bárány, I., Reitzner, M.: Central limit theorems for random polytopes in convex polytopes. manuscript (2007) BRSZ 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.
- I. Bárány and A. M. Vershik, On the number of convex lattice polytopes, Geom. Funct. Anal. 2 (1992), no. 4, 381–393. MR 1191566, DOI 10.1007/BF01896660
- Imre Bárány and Van Vu, Central limit theorems for Gaussian polytopes, Ann. Probab. 35 (2007), no. 4, 1593–1621. MR 2330981, DOI 10.1214/009117906000000791 bla1 Blaschke, W.: Über affine Geometrie XI: L’̈osung des “Vierpunktproblem” von Sylvester aus der Theorie der geometrischen Wahrscheinlichkeiten. Leipziger Berichte, 69 (1917), 436–453. bla2 Blaschke, W.: Affine Differentialgeometrie. Springer, Berlin, (1923).
- H. Bräker, T. Hsing, and N. H. Bingham, On the Hausdorff distance between a convex set and an interior random convex hull, Adv. in Appl. Probab. 30 (1998), no. 2, 295–316. MR 1642840, DOI 10.1239/aap/1035228070
- Christian Buchta, On a conjecture of R. E. Miles about the convex hull of random points, Monatsh. Math. 102 (1986), no. 2, 91–102. MR 861933, DOI 10.1007/BF01490202
- Christian Buchta, An identity relating moments of functionals of convex hulls, Discrete Comput. Geom. 33 (2005), no. 1, 125–142. MR 2105754, DOI 10.1007/s00454-004-1109-3
- A. J. Cabo and P. Groeneboom, Limit theorems for functionals of convex hulls, Probab. Theory Related Fields 100 (1994), no. 1, 31–55. MR 1292189, DOI 10.1007/BF01204952
- Pierre Calka and Tomasz Schreiber, Large deviation probabilities for the number of vertices of random polytopes in the ball, Adv. in Appl. Probab. 38 (2006), no. 1, 47–58. MR 2213963, DOI 10.1239/aap/1143936139
- W. Cook, M. Hartmann, R. Kannan, and C. McDiarmid, On integer points in polyhedra, Combinatorica 12 (1992), no. 1, 27–37. MR 1167473, DOI 10.1007/BF01191202
- Bradley Efron, The convex hull of a random set of points, Biometrika 52 (1965), 331–343. MR 207004, DOI 10.1093/biomet/52.3-4.331
- B. Efron and C. Stein, The jackknife estimate of variance, Ann. Statist. 9 (1981), no. 3, 586–596. MR 615434
- H. Groemer, On the mean value of the volume of a random polytope in a convex set, Arch. Math. (Basel) 25 (1974), 86–90. MR 341286, DOI 10.1007/BF01238645
- Piet Groeneboom, Limit theorems for convex hulls, Probab. Theory Related Fields 79 (1988), no. 3, 327–368. MR 959514, DOI 10.1007/BF00342231 Ho Hostinsky, B.: Sur les probabilités géométriques. Publ. Fac. Sci. Univ. Brno (1925).
- J. F. C. Kingman, Random secants of a convex body, J. Appl. Probability 6 (1969), 660–672. MR 254891, DOI 10.1017/s0021900200026693
- Tailen Hsing, On the asymptotic distribution of the area outside a random convex hull in a disk, Ann. Appl. Probab. 4 (1994), no. 2, 478–493. MR 1272736
- Ravi Kannan and László Lovász, Covering minima and lattice-point-free convex bodies, Ann. of Math. (2) 128 (1988), no. 3, 577–602. MR 970611, DOI 10.2307/1971436
- A. Ya. Hinčin, A quantitative formulation of the approximation theory of Kronecker, Izvestiya Akad. Nauk SSSR. Ser. Mat. 12 (1948), 113–122 (Russian). MR 0024925
- Jeong Han Kim and Van H. Vu, Concentration of multivariate polynomials and its applications, Combinatorica 20 (2000), no. 3, 417–434. MR 1774845, DOI 10.1007/s004930070014
- S. V. Konyagin and K. A. Sevast′yanov, Estimate of the number of vertices of a convex integral polyhedron in terms of its volume, Funktsional. Anal. i Prilozhen. 18 (1984), no. 1, 13–15 (Russian). MR 739085
- K.-H. Küfer, On the approximation of a ball by random polytopes, Adv. in Appl. Probab. 26 (1994), no. 4, 876–892. MR 1303867, DOI 10.2307/1427895
- R. E. Miles, Isotropic random simplices, Advances in Appl. Probability 3 (1971), 353–382. MR 309164, DOI 10.2307/1426176
- Mathew D. Penrose and J. E. Yukich, Normal approximation in geometric probability, Stein’s method and applications, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 5, Singapore Univ. Press, Singapore, 2005, pp. 37–58. MR 2201885, DOI 10.1142/9789812567673_{0}003
- Shlomo Reisner, Carsten Schütt, and Elisabeth Werner, Dropping a vertex or a facet from a convex polytope, Forum Math. 13 (2001), no. 3, 359–378. MR 1831090, DOI 10.1515/form.2001.012
- Matthias Reitzner, The combinatorial structure of random polytopes, Adv. Math. 191 (2005), no. 1, 178–208. MR 2102847, DOI 10.1016/j.aim.2004.03.006
- Matthias Reitzner, Random polytopes and the Efron-Stein jackknife inequality, Ann. Probab. 31 (2003), no. 4, 2136–2166. MR 2016615, DOI 10.1214/aop/1068646381
- Matthias Reitzner, Central limit theorems for random polytopes, Probab. Theory Related Fields 133 (2005), no. 4, 483–507. MR 2197111, DOI 10.1007/s00440-005-0441-8
- Yosef Rinott, On normal approximation rates for certain sums of dependent random variables, J. Comput. Appl. Math. 55 (1994), no. 2, 135–143. MR 1327369, DOI 10.1016/0377-0427(94)90016-7
- A. Rényi and R. Sulanke, Über die konvexe Hülle von $n$ zufällig gewählten Punkten, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1963), 75–84 (1963) (German). MR 156262, DOI 10.1007/BF00535300
- Luis A. Santaló, Integral geometry and geometric probability, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR 0433364
- Wolfgang M. Schmidt, Integer points on curves and surfaces, Monatsh. Math. 99 (1985), no. 1, 45–72. MR 778171, DOI 10.1007/BF01300739
- Rolf Schneider and John André Wieacker, Random polytopes in a convex body, Z. Wahrsch. Verw. Gebiete 52 (1980), no. 1, 69–73. MR 568260, DOI 10.1007/BF00534188
- Carsten Schütt, Random polytopes and affine surface area, Math. Nachr. 170 (1994), 227–249. MR 1302377, DOI 10.1002/mana.19941700117
- Ya. G. Sinaĭ, A probabilistic approach to the analysis of the statistics of convex polygonal lines, Funktsional. Anal. i Prilozhen. 28 (1994), no. 2, 41–48, 96 (Russian, with Russian summary); English transl., Funct. Anal. Appl. 28 (1994), no. 2, 108–113. MR 1283251, DOI 10.1007/BF01076497 su Sulanke, R.: Letter to the author, 2004 syl Sylvester, J.J.: Question 1491. Educational Times, London, April (1864). syl2 Sylvester, J.J.: Report of the British Association, 35 (1865), 8–9.
- Pavel Valtr, The probability that $n$ random points in a triangle are in convex position, Combinatorica 16 (1996), no. 4, 567–573. MR 1433643, DOI 10.1007/BF01271274
- A. M. Vershik, The limit form of convex integral polygons and related problems, Funktsional. Anal. i Prilozhen. 28 (1994), no. 1, 16–25, 95 (Russian, with Russian summary); English transl., Funct. Anal. Appl. 28 (1994), no. 1, 13–20. MR 1275724, DOI 10.1007/BF01079006
- A. Vershik and O. Zeitouni, Large deviations in the geometry of convex lattice polygons, Israel J. Math. 109 (1999), 13–27. MR 1679585, DOI 10.1007/BF02775023
- Van H. Vu, On the concentration of multivariate polynomials with small expectation, Random Structures Algorithms 16 (2000), no. 4, 344–363. MR 1761580, DOI 10.1002/1098-2418(200007)16:4<344::AID-RSA4>3.0.CO;2-5
- V. H. Vu, Concentration of non-Lipschitz functions and applications, Random Structures Algorithms 20 (2002), no. 3, 262–316. Probabilistic methods in combinatorial optimization. MR 1900610, DOI 10.1002/rsa.10032
- V. H. Vu, Sharp concentration of random polytopes, Geom. Funct. Anal. 15 (2005), no. 6, 1284–1318. MR 2221249, DOI 10.1007/s00039-005-0541-8
- Van Vu, Central limit theorems for random polytopes in a smooth convex set, Adv. Math. 207 (2006), no. 1, 221–243. MR 2264072, DOI 10.1016/j.aim.2005.11.011
- Wolfgang Weil and John A. Wieacker, Stochastic geometry, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 1391–1438. MR 1243013 wie Wieacker, J.A.: Einige Probleme der polyedrische approximation. Diplomarbeit, Albert-Ludwigs-Universität, Freiburg im Breisgau, (1978)
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
- MR Author ID: 30885
- Email: barany@renyi.hu, barany@math.ucl.ac.uk
- Received by editor(s): November 2, 2007
- Published electronically: April 25, 2008
- © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2402946