Random points and lattice points in convex bodies

Bárány, Imre

doi:10.1090/S0273-0979-08-01210-X

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

Discrete Comp. Geom.

30

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

69

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

Publ. Fac. Sci. Univ. Brno

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

35

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