Empty convex polytopes in random point sets

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Empty convex polytopes in random point sets József Balogh∗1, Hernán González-Aguilar†2, and Gelasio Salazar‡3 1Department of Mathematics, University of Illinois at Urbana-Champaign. Urbana, IL, United States. 2Facultad de Ciencias, Universidad Autónoma de San Luis Potosí. San Luis Potosí, SLP, México. 3Instituto de Física, Universidad Autónoma de San Luis Potosí. San Luis Potosí, SLP, México. Abstract Given a set Pof points in Rd, a convex hole (alternatively, empty convex polytope) of Pis a convex polytope with vertices in P, containing no points of P in its interior. Let Rbe a bounded convex region in Rd. We show that if Pis a set of nrandom points chosen independently and uniformly over R, then the expected number of vertices of the largest hole of P is Θ(log n/(log log n)), regardless of the shape of R. This generalizes the analogous result proved for the case d= 2 by Balogh, González-Aguilar, and Salazar. Introduction Given a set Pof points in Rd, a convex hole (alternatively, empty convex polytope) of Pis a convex polytope with vertices in P, containing no points of Pin its interior. Recently, we showed that the expected size of the largest convex hole in a random n-point set in the plane is Θ(log n/ log log n)[3]. One anonymous referee of this paper asked if this could be generalized to d > 2dimensions. Joe O’Rourke asked the same question in MathOverflow, and Douglas Zare replied that the Ω(log n/ log log n)lower bound carries over easily to the d-dimensional case [10]. At the end of his reply, Zare wrote: “I don’t know whether their harder upper bound of the same form also extends to higher dimensions, but I suspect that it does.” Our aim in this note is to show that, indeed, the upper bound also holds for higher dimensions. Thus, our main result is: Theorem 1 Let d≥2be an integer, and let Rbe a bounded convex region in Rd. Let Rnbe a set of n points chosen independently and uniformly at random from R, and let Hol(Rn)denote the random variable ∗Email: [email protected]. Research supported by NSF CAREER Grant DMS-0745185. †Email: [email protected]. Research supported by PROMEP. ‡Email: [email protected]. Research supported by CONACYT Grant 106432. that measures the number of vertices of the largest convex hole in Rn. Then E(Hol(Rn)) = Θlog n log log n. Moreover, a.a.s. Hol(Rn)=Θlog n log log n. The proof, which is an immediate consequence of Theorems 2 and 3 below, follows very closely the main ideas of the proof of [3, Theorem 3]. Indeed, the strategy and the main ideas are so close that it seems best to follow as closely as possible the structure of [3]. As we shall see below, some of the results proved in [3] follow without any modification to arbitrary dimensions. The main adaptations needed are: 1. a generalization of the results in [3, Section 2] to d > 2dimensions, to approximate convex sets in Rdwith lattice polytopes; and 2. an adaptation to d > 2dimensions of the results on the probability that a random n-point set is in convex position, from the exact results of Valtr [11, 12] in R2to the asymptotic results of Bárány [6] in Rd, for any d≥2. The workhorse for the proof of Theorem 1 for arbitrary regions Ris the following statement, which takes care of the particular case in which Ris a parallelotope. Theorem 2 Let Rbe a parallelotope in Rd. Let Rn be a set of npoints chosen independently and uniformly at random from R, and let Hol(Rn)denote the random variable that measures the number of vertices of the largest convex hole in Rn. Then E(Hol(Rn)) = Θlog n log log n. Moreover, a.a.s. Hol(Rn)=Θlog n log log n. 85 Empty convex polytopes in random point sets The other essential fact is that the order of magnitude of the expected number of vertices of the largest convex hole is independent of the shape of R: Theorem 3 There exist absolute constants b, b0with the following property. Let Rand Sbe bounded convex regions in Rd. Let Rn(respectively, Sn) be a set of n points chosen independently and uniformly at random from R(respectively, S). Let Hol(Rn)(respectively, Hol(Sn)) denote the random variable that measures the number of vertices of the largest convex hole in Rn (respectively, Sn). Then, for all sufficiently large n, b≤E(Hol(Rn)) E(Hol(Sn)) ≤b0. Moreover, there exist absolute constants c, c0such that a.a.s. c≤Hol(Rn) Hol(Sn)≤c0. We remark that Theorem 3 is in line with the following result proved by Bárány and Füredi [5]: the expected number of empty simplices in a set of npoints chosen uniformly and independently at random from a convex set Awith non-empty interior in Rdis Θ(nd), regardless of the shape of A. Remark (Proof of Theorem 1). Theorem 1 is an immediate consequence of Theorems 2 and 3. The proof of Theorem 2 is in Section 1. As we explain in Section 2, the proof of Theorem 3 is totally analogous to the proof of [3, Theorem 2]. We make a few final remarks before we move on to the proofs. For the rest of the paper we let Vol(U) denote the volume of a region Uin Rd. We also note that, throughout the paper, by log xwe mean the natural logarithm of x. Finally, since we only consider sets of points chosen independently and uniformly at random from a region, for brevity we simply say that such point sets are chosen at random from this region. 1 Proof of Theorem 2 We start by noting that if Q, Q0are two regions such that Q0is obtained from Qby an affine transformation, then Hol(Qn) = Hol(Q0 n). Thus we may assume without loss of generality that Ris the isothetic unit area square centered at the origin. We prove the lower and upper bounds separately. More specifically, we prove that for all sufficiently large n: PrHol(Rn)≥1 2 log n log log n≥1−n−2.(1) PrHol(Rn)≤d(2 + 2d2)log n log log n≥1−n−1.(2) We note that (1) and (2) imply immediately the a.a.s. part of Theorem 2. Now the Ω(log n/ log log n) part of the theorem follows from (1), since Hol(Rn) is a non-negative random variable, whereas the O(log n/ log log n)part follows from (2), since Hol(Rn)is bounded by above by n. Thus we complete the proof by showing (1) and (2). Proof of (1) Let Rnbe a set of npoints chosen at random from R. We prove that a.a.s. Rnhas an empty convex polytope of size at least log n 2 log log n. Consider the 2-dimensional projection π: Rd→R2defined by (x1, x2, x3, x4, . . . , xd)→ (x1, x2,0,0,...,0). Note that π(Rn)is a set of n points chosen (independently and uniformly) at random from the unit square. Thus it follows from Eq. (1) in [3] that a.a.s. π(Rn)has a convex hole Hof size at least log n 2 log log n. Clearly, π−1(H)is an empty convex polytope of Rnof size at least log n 2 log log n. Proof of (2) Let Rnbe a set of npoints chosen at random from R. We remark that throughout the proof we always implicitly assume that nis sufficiently large. We shall use the following easy consequence of Chernoff’s bound. This is derived immediately, for instance, from Theorem A.1.11 in [1]. Lemma 4 Let Y1, . . . , Ymbe mutually independent random variables with Pr(Yi= 1) = pand Pr(Yi= 0) = 1 −p, for i= 1, . . . , m. Let Y:= Y1+. . . +Ym. Then PrY≥(3/2)pm< e−pm/16. Let Sbe the isothetic d-cube of volume 3d, also (as R) centered at the origin. We need the following result on approximating convex sets by lattice parallelotopes. Claim A. For each positive integer d > 0there exist integers f1(d)and f2(d)with the following property. Let Hbe a convex set in Rd. Then there exists a lattice parallelotope Q1such that H⊆Q1and Vol(Q1)≤(f1(d)+1) Vol(H). Moreover, if Vol(H)≥ 2d−1·1000/n, then there is a lattice parallelotope Q0 such that Q0⊆Hand Vol(Q0)≥(f2(d)−1)Vol(H). Sketch of Proof. By a the theorem of M. Balla [2], for every convex compact set H⊂Rdthere exists a parallelotope Psuch that P⊂H⊂dP =b Pwhere dP is the image of Punder a homothety with ratio d. This implies that d−dVol(P)≤Vol(H)≤ddVol(P). For each vertex vi,i= 0,...,2d, of b P, let us denote by Qvithe parallelotope with side length 2/n with 86 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 facets parallel to the facets of b Pthat has vias one of its vertices and b P∩Qvi={vi}. Observe that each Qvi contains a d-ball of diameter 2/n and for that, there is a lattice point v0 iin the interior of each Qvi. Let Q1 be the convex hull of the points v0 1, . . . , v0 2d. Note that d(vi, v0 i)≤2 n√dfor each i= 1,...,2d, this implies that %(b P, Q1)≤2 n√dwhere %(·,·)is the Hausdorff metric. Then Vol(Q1)≤Vol(b P) + 2 n√d·Surf(b P) + Vol(B) ≤ddVol(H) + 2 n√d·Surf(b P) + Vol(B) ≤(f1(d) + 1) Vol(H) where Bis the d-ball of diameter 2 n√dand Surf(·)is the volume (d−1)-dimensional. Now, for each vertex wi,i= 0,...,2d, of Pconsider the parallelotope Qwiwith side length 2/n with facets parallel to the facets of Pthat has wias one of its vertices and Qwi⊂P. Because each Qwicontains a d-ball of diameter 2 n, then there exists a lattice point in each Qwi, let w0 ithis point. The existence of these points is guaranteed provided that Vol(H)≥ 2d−1·1000/n Let Q0be the convex hull of the points w0 1, . . . , w0 2d. Note that d(wi, w0 i)≤2 n√dfor each i= 1,...,2d, this implies that %(P, Q0)≤2 n√d. Then Vol(P)−2 n√d·Surf(Q0)−Vol(B)≤Vol(Q0)This implies Vol(Q0)≥Vol(P)−2 n√d·Surf(Q0)−Vol(B) ≥Vol(P)−2 n√d·Surf(P)−Vol(B) ≥d−dVol(H)−2 n√d·Surf(H)−Vol(B) ≥(f2(d)−1)Vol(H). For the rest of the proof, for simplicity we define f3(d) := f3(d), where f1(d)and f2(d)are as in Claim A. Since there are (9n+ 1)d<(10n)dlattice points, out of which (n+ 1)dare in R, it follows that there are fewer than (10n)d 2d<(10n)d2dlattice dparallelotopes in total, and fewer than nd 2d< nd2d lattice d-parallelotopes all of whose vertices are in R. Claim B. With probability at least 1−n−10 every lattice parallelotope Qwith Vol(Q)<20f3(d) log n/n satisfies that |Rn∩Q| ≤ (3/2) ·20f3(d) log n. Proof. We note that, since (f1(d) + 1)/f2(d)>1, it follows that 20f3(d)> d2d+ 10. Let Qbe a lattice parallelotope with Vol(Q)<20 f3(d) log n/n, and let Z=Z(Q)⊆Rbe any lattice parallelotope containing Q, with Vol(Z) = 20 f3(d) log n/n. Let XQ (respectively, XZ) denote the random variable that measures the number of points of Rnin Q(respectively, Z). We apply Lemma 4 with p=Vol(Z)and m=n, to obtain Pr(XZ≥(3/2) ·20 f3(d) log n)< e−(3/2)20 f3(d)/24 log n=n−(5/4)f3(d). Since Q⊆Z, it follows that Pr(XQ≥(3/2) ·20 f3(d) log n)< n−(5/4)f3(d). As the number of choices for Qis at most (10n)d2d, with probability at least (1−(10n)d2d· n−(5/4)f3(d))>1−n−10, no such Qcontains more than (3/2) ·20 f3(d) log npoints of Rn. A polytope is empty if its interior contains no points of Rn. Claim C. With probability at least 1−n−10, there is no empty lattice parallelotope Q⊆Rwith Vol(Q)≥ 20 (d2d+ 10) log n/n. Proof. The probability that a fixed lattice parallelotope Q⊆Rwith Vol(Q)≥d2d+ 10 log n/n is empty is (1 −Vol(Q))n< n−d2d+10.Since there are fewer than nd2dlattice parallelotopes in R, it follows that the probability that at least one of the lattice parallelotope with area at least (d2d+ 10) log n/n (and hence with area at least 20 (d2d+ 10) log n/n) is empty is less than nd2d·n−(d2d+10)≤n−10. For the rest of the proof, we let Hbe a maximum size convex hole of Rn. Claim D. With probability at least 1−n−10 we have Vol(Q1)< f3(d) log n/n. Proof. Suppose first that Vol(H)<2d−11000/n. Then Vol(Q1)≤2d−1·1000(f1(d) + 1)/n. Since this is obviously smaller than f3(d) log n/n, in this case we are done. Now suppose that Vol(H)≥ 2d−1·1000/n, so that Q0(from Claim A) exists. Moreover, Vol(Q1)≤(f1(d) + 1)Vol(H). Since Q0⊆H, and His a hole of Rn, it follows that Q0is empty. Thus, by Claim C, with probability at least 1−n−10 we have that Vol(Q0)< (d2d+ 10) log n/n. Now since Vol(Q1)<(f1(d) + 1) Vol(H)and Vol(Q0)≥f2(d)·Vol(H), it follows that Vol(Q1)≤(f1(d) + 1) Vol(Q0)/f2(d). Thus with probability at least 1−n−10 we have that Vol(Q1)≤(f1(d) + 1)(d2d+ 10)/f2(d)log n/n = f3(d) log n/n. Claim E. For each fixed integer d > 0, there exist a universal positive constant c2:= c2(d)with the following property. Let Kbe any convex polytope in Rd. Then the probability that rpoints chosen at random from Kare in convex position is at most (c2n2 d−1)−n. Proof. This is an immediate consequence of [6] (see for instance [4, Theorem 2.1]).  87 Empty convex polytopes in random point sets Claim F. With probability at least 1−2n−2the random point set Rnsatisfies that no lattice parallelotope Qwith Vol(Q)<20 f3(d) log n/n contains d(2 + 2d2) log n/(log log n)points of Rnin convex position. Proof. Let Qbe a lattice parallelotope with Vol(Q)<20 f3(d) log n/n. By Claim B, with probability at least 1−n−10 we have |Rn∩Q| ≤ (3/2) · 20 f3(d) log n. Thus it suffices to show that the probability that there exists a lattice parallelotope Qwith with |Rn∩Q| ≤ (3/2) ·20 f3(d) log nand d(2 + 2d2) log n/(log log n)points of Rnin convex position is at most n−2. Let c2:= c2(d)be as in Claim E. Thus the expected number of r-tuples of Rnin Qin convex position is at most |Rn∩Q| rc2r2 d−1−r ≤(3/2) ·f3(d) log n rc2r2 d−1−r ≤e·(3/2) ·F2log n rrc2r2 d−1−r <c3log n·r−1−2 d−1r, where c3:= 3ef3(d)/2c2. Since there are at most nd2dchoices for Q, it follows that the expected total number of such rtuples with r=d(2 + 2d2) log n/ log log nis at most nd2d·c3log n·r−1−2 d−1r< n−2(this last inequality follows from an elemenary but long manipulation). This completes the proof, since it follows that the probability that such an r-tuple exists is at most n2. To finish the proof of (2), recall that His a maximum size empty convex polytope of Rn, and that H⊆ Q1. It follows immediately from Claims D and F that with probability at least 1−n−1the parallelotope Q1 does not contain a set of d(2 + 2d2) log n/(log log n) points of Rnin convex position. In particular, with probability at least 1−n−1the size of His at most d(2 + 2d2) log n/(log log n). 2 Proof of Theorem 3 The proof of Theorem 3 is totally analogous to the proof of [3, Theorem 2]. Indeed, in that proof, essentially all the arguments are independent of the dimension. The only adaptation that needs to be done is that we need a version of [3, Corollary 6] for d > 2dimensions. We recall that [3, Corollary 6] claims that if His a closed convex set in R2, then there exist rectangles U, K such that U⊆H⊆K, Vol(U)≥Vol(H)/8, and Vol(K)≤2Vol(H). Ad-dimensional analogue of this statement follows from the following result in [9]: if His a convex body in Rd, then Hcontains a parallelotope Psuch that some translate of dP contains K. Indeed, this implies at once that if His a closed convex set in Rd, then there exist parallelotopes U, K such that U⊆H⊆K, Vol(U)≥Vol(H)/d, and Vol(K)≤d·Vol(H). References [1] N. Alon and J. Spencer. The probabilistic method, 3rd. Edition. Wiley, 2008. [2] M. Y. Balla, Approximation of convex bodies by parallelotopes, Internal Report IC/87/310, International Centre for Theoretical Physics, ICTP, Trieste, 1988 [3] J. Balogh, H. González-Aguilar, and G. Salazar, Large convex holes in random point sets. Comp. Geom. 46 (2013), 725–733. [4] I. Bárány, Random points, convex bodies, lattices. Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), 527–535. Higher Ed. Press, Beijing, 2002. [5] I. Bárány and Z. Füredi, Empty simplices in Euclidean space, Canad. Math. Bull. 30 (1987) 436–445. [6] I. Bárány, A note on Sylvester’s four-point problem. Studia Sci. Math. Hungar. 38 (2001), 73–77. [7] I. Bárány, Sylvester’s question: the probability that n points are in convex position, Ann. Probab. 27 (1999), 2020–2034. [8] I. Bárány and P. Valtr, Planar point sets with a small number of empty convex polygons. Studia Sci. Math. Hungar. 41 (2004), 243–266. [9] G.D. Chakerian and S. K. Stein, Some intersection properties of convex bodies. Proc. Amer. Math. Soc. 18 (1967), 109–112. [10] J. O’Rourke, Empty convex polytopes for random point sets. http://mathoverflow.net/questions/107875 (2012). [11] P. Valtr, Probability that nRandom Points are in Convex Position. Discrete and Computational Geometry 13 (1995), 637–643. [12] P. Valtr, The Probability that nRandom Points in a Triangle Are in Convex Position. Combinatorica 16 (1996), 567–573. 88