On k-gons and k-holes in point sets

On k-Gons and k-Holes in Point Sets∗ Oswin Aichholzer†Ruy Fabila-Monroy‡Hern´an Gonz´alez-Aguilar § Thomas Hackl†Marco A. Heredia ¶Clemens HuemerkJorge Urrutia∗∗ Pavel Valtr†† Birgit Vogtenhuber† August 29, 2014 Abstract We consider a variation of the classical Erd˝os-Szekeres problems on the existence and number of convex k-gons and k-holes (empty k-gons) in a set of npoints in the plane. Allowing the k-gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any kand sufficiently large n, we give a quadratic lower bound for the number of k-holes, and show that this number is maximized by sets in convex position. 1 Introduction Let Sbe a set of npoints in general position in the plane (i.e, no three points of Sare collinear). A k-gon is a simple polygon spanned by kpoints of S. A k-hole is an empty k-gon; that is, a k-gon that contains no points of Sin its interior. Around 1933 Esther Klein raised the following question, which was (partially) answered in the classical paper by Erd˝os and Szekeres [19] in 1935: “Is it true that for any kthere is a smallest integer g(k) such that any set of g(k) points contains at least one convex k-gon?” As observed by Klein, g(4) = 5, and Kalbfleisch et al. [30] proved that g(5) = 9. The case k= 6 was only solved as recently as 2006 by Szekeres and Peters [36]. They showed that g(6) = 17 by an exhaustive computer search. The well known Erd˝os–Szekeres Theorem [19] states that g(k) is finite for any k. The current best bounds are 2k−2+ 1 ≤g(k)≤2k−5 k−2+ 1 for k≥5, where the lower bound goes back to Erd˝os and Szekeres [20] and is conjectured to be tight. There have been many improvements on the upper bound, where the currently best bound has been obtained in 2005 by T´oth and Valtr [37]; see e.g. [3] for more details. Erd˝os and Guy [18] posed the following generalization: “What is the least number of convex k-gons determined by any set Sof npoints in the plane?” The trivial solution for the case k= 3 is n 3. For convex 4-gons this question is highly non-trivial, as it is related to the search for the rectilinear crossing number cr(n), the minimum number of crossings in a straight-line drawing of the complete graph with nvertices; see the next section for details. ∗Research of Oswin Aichholzer and Birgit Vogtenhuber supported by the ESF EUROCORES programme EuroGIGA – CRP ‘ComPoSe’, Austrian Science Fund (FWF): I648-N18. Research of Ruy Fabila-Monroy partially supported by CONACyT (Mexico), grant 153984. Research of Thomas Hackl supported by the Austrian Science Fund (FWF): P23629-N18 ‘Combinatorial Problems on Geometric Graphs’. Research of Clemens Huemer partially supported by projects MTM201230951 and Gen. Cat. DGR 2009SGR1040. Research of Marco Antonio Heredia, Hern´an Gonz´alez-Aguilar, and Jorge Urrutia partially supported by CONACyT (Mexico), grant CB-2007/80268. Work by Pavel Valtr supported by project 1M0545 of the Ministry of Education of the Czech Republic. †Institute for Software Technology, University of Technology, Graz, Austria, [oaich|thackl|bvogt]@ist.tugraz.at ‡Departamento de Matem´aticas, Cinvestav, D.F. M´exico, M´exico, [email protected] §Facultad de Ciencias, Universidad Aut´onoma de San Luis Potos´ı, San Luis Potos´ı, M´exico, [email protected] ¶Departamento de Sistemas, Universidad Aut´onoma Metropolitana - Azcapotzalco, D.F. M´exico, M´exico, [email protected] kDepartament de Matem`atica Aplicada IV, Universitat Polit`ecnica de Catalunya, Barcelona, Spain, [email protected] ∗∗Instituto de Matem´aticas, Universidad Nacional Aut´onoma de M´exico, D.F. M´exico, M´exico, [email protected] ††Department of Applied Mathematics and Institute for Computer Science (ITI), Charles University, Prague, Czech Republic 1 In 1978 Erd˝os [17] raised the following question for convex k-holes: “What is the smallest integer h(k) such that any set of h(k) points in the plane contains at least one convex k-hole?” As observed by Esther Klein, every set of 5 points determines a convex 4-hole, and Harborth [27] showed that 10 points always contain a convex 5-hole. Surprisingly, in 1983 Horton showed that there exist arbitrarily large sets of points containing no convex 7-hole [29]. It took almost a quarter of a century after Horton’s construction to answer the existence question for k= 6. In 2007/08 Nicol´as [33] and independently Gerken [26] proved that every sufficiently large point set contains a convex 6-hole; see also [40]. A natural generalization of the existence question for k-holes is this: “What is the least number hk(n) of convex k-holes determined by any set of npoints in the plane?” Horton’s construction implies hk(n) = 0 for k≥7. Table 1 shows the current best lower and upper bounds for k= 3,...,6. n2−32 7n+22 7≤h3(n)≤1.6196n2+o(n2) n2 2−9 4n−o(n)≤h4(n)≤1.9397n2+o(n2) 3n 4−o(n)≤h5(n)≤1.0207n2+o(n2) n 229 −4≤h6(n)≤0.2006n2+o(n2) Table 1: Bounds on the numbers hk(n) of convex k-holes [7, 12, 41]. All upper bounds in the table are due to B´ar´any and Valtr [12]. They are obtained by improving constructions that had been developed by Dumitrescu [15] and previously improved by Valtr [39]. Concerning the lower bounds for k≤5, Dehnhardt [14] showed in his PhD thesis that for n≥13, h3(n)≥n2−5n+ 10, h4(n)≥n−3 2+ 6, and h5(n)≥3n 12 . As this PhD thesis was published in German and is not easy to access, later on several weaker bounds have been published. Only very recently these results have been subsequently improved [23, 24, 8, 9, 41, 7], where the currently best bounds can be found in [7], using a remarkable result from [24]. A result of independent interest is by Pinchasi et al. [34], who showed h4(n)≥h3(n)−n2 2−O(n) and h5(n)≥h3(n)−n2−O(n). By this, improving the n2-factor in the lower bound of h3(n) implies better lower bounds also for h4(n) and h5(n). Concerning lower bounds on the number of 6-holes, a proof of h6(n)≥ bn−1 858 c−2 is contained in the proceedings version [5] of the paper at hand. This proof is based on h6(1717) ≥1 by Gerken [26]. Valtr [41] presented an improved bound of h6(n)≥n 229 −4, combining a different proof technique with Koshelev’s result of h6(463) ≥1 [31]. As combining this result by Koshelev with the proof of [5] only gives h6(n)≥n 231 −O(1), the according proof is omitted here. In this paper we generalize the above questions on the numbers of k-gons and k-holes by allowing the gons/holes to be non-convex. Thus, whenever we refer to a (general) k-gon or k-hole, unless it is specifically stated to be convex or non-convex, it could be either. Similar results for 4-holes and 5-holes can be found in [6] and [9], respectively. The PhD thesis [42] summarizes most results obtained for k≥4. See also [3] for a survey on the history of questions and results about k-gons and k-holes. We remark that in some related literature, k-holes are assumed to be convex. A set of kpoints in convex position spans precisely one convex k-hole. In contrast, a point set might admit exponentially many different polygonizations (spanning cycles) [25]. Thus, the number of k-gons and k-holes can be larger than n k, which makes the questions considered in this paper more challenging (and interesting) than they might appear at first glance. Tables 2 and 3 summarize the best current bounds on the numbers of k-gons and k-holes, including the results of this paper. The entries in the tables list lower and upper bounds, also in explicit form if available, thus indicating for which values there are still gaps to close. Among other results, we generalize properties concerning 4-holes [6] and 5-holes [9] to k≥6. In Section 2.1 we give asymptotic bounds on the number of non-convex and general k-gons. In Section 3 we consider (general) k-holes. We show that for sufficiently small kwith respect to ntheir number is maximized by sets in convex position, which is not the case for large k. Section 4 provides a tight bound for the maximum number of non-convex k-holes, and Section 5 contains bounds for the minimum number of general k-holes. We conclude with open problems in Section 6. 2 convex non-convex general min max min max k=4 cr(n) Θ(n4) 3n 4−3 cr(n) Θ(n4) [9] n 4 Θ(n4) [9] 3n 4−2 cr(n) Θ(n4) [9] k=5 Θ(n5) [13] 10n 5−2(n−4) cr(n) Θ(n5) [9] n 5 Θ(n5) [9] Θ(n5) [Sec. 2.1] k≥6Θ(nk) [13] Θ(nk) [Sec. 2.1] n k Θ(nk) [Sec. 2.1] Θ(nk) [Sec. 2.1] Table 2: Bounds on the numbers of convex, non-convex, and general k-gons for npoints and constant k. convex non-convex general min max min max k=4 ≥n2 2−9 4n−o(n) ≤1.9397n2+o(n2) Θ(n2) [7,12] ≤n3 2−O(n2) ≥n3 2−O(n2log n) Θ(n3) [6] ≥5 2n2−O(n) ≤O(n5 2log n) Ω(n2) [6], O(n5 2log n) [Sec. 5] n 4 Θ(n4) [6] k=5 ≥3n 4−o(n) ≤1.0207n2+o(n2) Ω(n) [7], O(n2) [12] ≤n!/(n−4)! Θ(n4) [Sec. 4] ≥17n2−O(n) ≤O(n3(log n)2) Ω(n2) [9], O(n3(log n)2) [Sec. 5] n 5 Θ(n5) [9] k≥6 k=6:≥n 229 −4 Ω(n) [41] O(n2) [12] k≥7: ∅[29] ≤n!/(n−k+1)! Θ(nk−1) [Sec. 4] ≥n2−O(n) ≤O(nk+1 2(log n)k−3) Ω(n2), O(nk+1 2(log n)k−3) [Sec. 5] n k Θ(nk) [Sec. 3] Table 3: Bounds on the numbers of convex, non-convex and general k-holes for npoints and constant k. 2 General k-gons 2.1 k-gons and the rectilinear crossing number For small values of k, the number of k-gons in a point set Sof npoints can be related to the rectilinear crossing number cr(S) of S. This is the number of proper intersections (i.e., intersections in the interior of edges) in the (drawing of the) complete straight-line graph on S. By cr(n) we denote the minimum possible rectilinear crossing number over all point sets of cardinality n. Determining cr(n) is a wellknown problem in discrete geometry; see [13, 18] as general references and [4] for bounds on small sets. Asymptotically we have cr(n) = c4n 4= Θ(n4), where c4is a constant in the range 0.379972 ≤c4≤ 0.380473. The currently best lower bound on c4is by ´ Abrego et al. [2, 1]. The upper bound stems from a recent work of Fabila-Monroy and L´opez [22]. It is easy to see that the number of convex 4-gons is equal to cr(S) and is thus minimized by sets realizing cr(n). Since four points in non-convex position span three non-convex 4-gons, we have at most 3n 4−3 cr(n)≈1.86n 4non-convex and at most 3n 4−2 cr(n)≈2.24n 4general 4-gons. These bounds are tight for point sets minimizing the rectilinear crossing number. A similar relation has been obtained for the number of non-convex 5-gons in [9]: Any set of npoints has at most 10n 5−2(n−4) cr(n)≈6.2n 5non-convex 5-gons. Again, this bound is achieved by sets minimizing the rectilinear crossing number. Note that the maximum numbers of non-convex 4and 5-gons exceed the maximum numbers of their convex counterparts. For the number of general 5-gons, 3 no such direct relation to cr(n) is possible, as already for n= 6 there exist point sets with the same number of crossings but different numbers of 5-gons [9]. Similarly, for k≥6, none of the three types of k-gons (convex, non-convex, and general) in a point set Scan be expressed as a function of cr(S). Still, we can use the rectilinear crossing number to obtain bounds on these numbers. Let gt k(S) be the number of k-gons of type t(convex, non-convex, or general) in a point set S. Proposition 1. Let k≥4, and let c1,c2, and xbe arbitrary fixed constants such that Inequality (1) holds for all sets S0with cardinality |S0|=k. c1≤gt k(S0) + x·cr(S0)≤c2(1) Then for every point set Swith |S|=n≥k, the following bounds hold for the number gt k(S)of k-gons of type tin S. gt k(S)≥c1·n k−x·n−4 k−4·cr(S) (2) gt k(S)≤c2·n k−x·n−4 k−4·cr(S) (3) Proof. Given some point set Swith npoints, consider all its n ksubsets of size k{Si⊆S:|Si|=k}. Then we have the following equations. X i cr(Si) = n−4 k−4·cr(S) (4) X i gt k(Si) = gt k(S) (5) Using the first inequality in (1), Equation (5) can be transformed to the lower bound gt k(S) = X i gt k(Si)≥X i (c1−x·cr(Si)) = c1·n k−x·X i cr(Si) which, by applying (4), gives the desired bound (2). Analogously, we obtain (3) if we combine the second inequality in (1) with Equations (4) and (5). If xis negative in Inequality (2), then the rectilinear crossing number cr(S) of Sadds to the lower bound. Thus we can replace it by the minimum over all point sets of size n, cr(n), and by this obtain a lower bound that is independent of S. Corollary 2. Assume that for some constants x≤0and c1arbitrary, the inequality c1≤gt k(S0)+x·cr(S0) is satisfied for all point sets S0with cardinality |S0|=k. Then for every point set Swith |S|=n≥kthe following lower bound holds for the number gt k(S)of k-gons of type tin S. gt k(S)≥c1·n k−x·n−4 k−4·c4n 4=c1−x·c4·k 4n k(6) Accordingly, if xis positive, we can generalize Inequality (3) to a general upper bound. Corollary 3. Assume that for some constants x≥0and c2arbitrary, the inequality c2≥gt k(S0)+x·cr(S0) is satisfied for all point sets S0with cardinality |S0|=k. Then for every point set Swith |S|=n≥k, the following upper bound applies to the number gt k(S)of k-gons of type tin S. gt k(S)≤c2−x·c4·k 4n k(7) In each of the bounds resulting from Proposition 1, either c1or c2is not used. So of course, for independent optimization of the two bounds, it might be helpful to consider the pairs (c1, x), and (c2, x) independently, with possibly different optimal values for x. On the other hand, optimizing all three values c1,c2, and xsimultaneously results in bounds that are more easy to compare. In the following we 4 optimize in these two different ways. On the one hand we try to minimize the difference between c1and c2to obtain most possibly small ranges for the number of (some type of) k-gons in sets with a certain rectilinear crossing number. On the other hand we independently optimize (c1, x) and (c2, x) in order to obtain general bounds (meaning bounds that are independent from the rectilinear crossing number of a given set) by applying Corollaries 2 and 3 . Note that concerning the general bounds, lower bounds only make sense for the classical question about convex k-gons, as the numbers of general and non-convex k-gons are minimized by sets in convex position. Similarly, general upper bounds for non-convex or (general) k-gons are of interest while the maximum number of convex k-gons is n k, again achieved by convex sets. Recall that the number of k-gons (of whatever type) in a point set Sonly depends on the combinatorial properties and thus on the order type OT(S) of the underlying point set S. Thus, we calculate pairs (gt k(OT),cr(OT )) for all possible order types OT of kpoints, this way obtaining all possible pairs (gt k(S0),cr(S0)) that can occur for any point set S0with |S0|=k. For the calculation, we use the order type database [10], that contains a complete list of the order types of up to 11 points. Having this, we can optimize the values c1,c2, and xthat fulfill (1), obtaining the according relations (2) and (3). Tables 4 and 5 show an overview of the resulting relations. Note that trivial bounds on the numbers of k-gons can be obtained by assuming the theoretic possible maximum number of k-gons for each k-tuple. As the maximum numbers of general / non-convex k-gons in a k-tuple are 8, 29, and 92 for k∈ {5,6,7}, the bounds in Table 5 all improve over these trivial bounds. −0.75n 5+ 0.25 ·(n−4) ·cr(S)≤gconv 5(S)≤ −0.25n 5+ 0.25 ·(n−4) ·cr(S) gnon−conv 5(S) = 10n 5−2·(n−4) ·cr(S) 9.25n 5−1.75 ·(n−4) ·cr(S)≤ggen 5(S)≤9.75n 5−1.75 ·(n−4) ·cr(S) −n 6+ 0.08˙ 3n−4 2·cr(S)≤gconv 6(S)≤ −0.25n 6+ 0.08˙ 3n−4 2·cr(S) 294 9n 6−22 9n−4 2·cr(S)≤gnon−conv 6(S)≤366 9n 6−22 9n−4 2·cr(S) 281 3n 6−7 3n−4 2·cr(S)≤ggen 6(S)≤36n 6−7 3n−4 2·cr(S) −1.1923076n 7+ 0.0384615n−4 3·cr(S)≤gconv 7(S)≤ −0.3461538n 7+ 0.0384615n−4 3·cr(S) 86.230769n 7−3.538461n−4 3·cr(S)≤gnon−conv 7(S)≤123.846153n 7−3.538461n−4 3·cr(S) 85.5n 7−3.5n−4 3·cr(S)≤ggen 7(S)≤123.5n 7−3.5n−4 3·cr(S) Table 4: Bounding the number of k-gons in an npoint set Svia its rectilinear crossing number cr(S). gnon−conv 5(S)≤(10 −10 ·c4)n 5≈6.20n 5 ggen 5(S)≤(9.75 −8.75 ·c4)n 5≈6.43n 5 gnon−conv 6(S), ggen 6(S)≤(36 −35 ·c4)n 6≈22.7n 6 gnon−conv 7(S)≤(123.846153 −123.846153 ·c4)n 7≈75.64n 7 ggen 7(S)≤(123.5−122.5·c4)n 7≈76.95n 7 Table 5: Bounding the number of k-gons in an npoint set Svia the constant c4of the (minimum) rectilinear crossing number cr(n), cr(n) = c4n 4. From the calculations it can be seen that for all sets of size k≤7, the point sets reaching the maximum number of general or non-convex k-gons are at the same time minimizing the number of crossings. The same is true for k= 8. But continuing the calculations until k= 9, it turns out that this is not true in general. The (combinatorially unique) point set containing the maximum number of 1282 general 9-gons has 38 crossings and thus does not reach the (minimum) rectilinear crossing number cr(9) = 36 [4]. 5 2.2 k-gons, polygonizations, and the double chain Polygonizations, also called spanning cycles, can be considered as k-gons of maximal size (i.e., k=n). Garc´ıa et al. [25] construct a point set with Ω(4.64n) spanning cycles, the so-called double chain DC(n), which is currently the best known minimizing example; see Figure 1. n 2points n 2points Figure 1: The so-called double chain DC(n). The upper bound on the number of spanning cycles of any n-point set was improved several times during the last years, most recently to O(68.664n) [16] and O(54.543n) [35], neglecting polynomial factors in the asymptotic expressions. The minimum is achieved by point sets in convex position, which have exactly one spanning cycle. For the number of general k-gons this implies a lower bound of n k, as well as an upper bound of O(54.543kn k. Hence, for constant k, any point set has Θ(nk) general k-gons. On the other hand, the double chain provides Ω(nk) non-convex k-gons, where k≥4 is again a constant. To see this, choose one vertex from the upper chain of DC(n) and k−1≥3 vertices from the lower chain of DC(n), and connect them to a simple, non-convex polygon. This gives at least n 2n/2 k−1= Ω(nk) non-convex k-gons. As the lower bound on the maximal number of non-convex k-gons asymptotically matches the upper bound on the maximal number of general k-gons, we obtain the following result. Proposition 4. For any constant k≥4, the number of non-convex k-gons in a set of npoints is bounded by O(nk). This is tight in the sense that there exist sets with Ω(nk)non-convex k-gons. 3 Maximizing the number of (general) k-holes In [6] it is shown that the number of 4-holes is maximized for point sets in convex position if nis sufficiently large. It was conjectured that this is true for any constant k≥4. The following theorem settles this conjecture in the affirmative. Theorem 5. For every k≥4and n≥2(k−1)!k 4+k−1, the number of k-holes is maximized by a set of npoints in convex position. Proof. Consider a non-convex k-hole H. For each of its non-extreme vertices (i.e., vertices not on the convex hull of H), there exists a triangle spanned by three extreme vertices of Hsuch that the nonextreme vertex is contained in the interior of the triangle. Further, there exists at least one reflex (and thus non-extreme) vertex vrof Hsuch that removing vrfrom the vertex set of H(and connecting its incident vertices) results in a simple non-empty (k−1)-gon. To see the latter, consider an edge eof CH(H) which is not in the boundary of H. Together with some part of the boundary of H,eforms a simple polygon H0that is interior-disjoint with H. For the case where H0is just a triangle, ecan be used to cut off the third vertex of H0from H. Clearly, the resulting (k−1)-gon is simple. If H0has at least four vertices then any triangulation of H0has at least two ears. For any ear not incident to e, the according diagonal of the triangulation can be used to cut off the central vertex of the ear from H. Again, the resulting (k−1)-gon is simple. Now consider a non-empty triangle ∆. We give an upper bound for the number of non-convex k-holes having the three vertices of ∆ as extreme points. Denote by Kthe set of simple non-empty (k−1)-gons having the vertices of ∆ on their convex hull. First, |K| can be bounded from above by the number of simple, possibly empty (k−1)-gons having the three vertices of ∆ on their boundary, that is, |K| ≤ (k−2)! 2n−3 k−4. 6 Further, every simple (k−1)-gon in Kmay be completed to a simple non-convex k-hole in at most k−1 ways by adding a reflex vertex: As the resulting polygon has to be empty, we have to use the inner geodesic connecting the two adjacent vertices of the (k−1)-gon. Only if this geodesic contains exactly one point, we do obtain one non-convex k-hole. Thus the number of non-convex k-holes having all vertices of ∆ on their convex hull is bounded from above by (k−1)(k−2)! 2n−3 k−4=(k−1)! 2n−3 k−4. Considering convex k-holes, observe that every k-tuple gives at most one convex k-hole. Denote by N the number of k-tuples that do not form a convex k-hole, and by Tthe number of non-empty triangles. Then we get (8) as a first upper bound on the number of (general) k-holes of a point set. n k−N+(k−1)! 2n−3 k−4·T(8) To obtain an improved upper bound from (8), we need to derive a good lower bound for N. To this end, consider again a non-empty triangle ∆. As ∆ is not empty, none of the n−3 k−3k-tuples that contain all three vertices of ∆ forms a convex k-hole. On the other hand, for such a k-tuple, all of its k 3 contained triangles might be non-empty. Thus, we obtain T·n−3 k−3/k 3as a lower bound for Nand (9) as an upper bound for the number of k-holes. n k+ (k−1)! 2n−3 k−4−n−3 k−3 k 3!·T(9) For n≥2(k−1)!k 4+k−1 this is at most n k, the number of k-holes of a set of npoints in convex position, which proves the theorem. The above theorem states that convexity maximizes the number of k-holes for k=O(log n log log n) and sufficiently large n. Moreover, the proof implies that any non-empty triangle in fact reduces the number of empty k-holes. Thus it follows that, for k=O(log n log log n) and nsufficiently large, the maximum number of convex k-holes is strictly larger than the maximum number of non-convex k-holes; see also the next section. At the other extreme, for k≈nthe statement does not hold: As already mentioned in the introduction, a set of kpoints spans at most one convex k-gon, but might admit exponentially many different nonconvex k-gons [25]. This leads to the question, for which kthe situation changes. The following theorem implies that for some 0 <c<1 and every k≥c·n, the convex set does not maximize the number of k-holes. Theorem 6. The number of k-holes in the double chain DC(n)on npoints is at least n−4 2 n−k 2·n−k+ 2 2·Ω(4.64k). Proof. Recall that Garc´ıa et al.[25] showed that the double chain on npoints (n/2 points on each chain) admits Ω(4.64n) polygonizations. To estimate the number of k-holes of the double chain on npoints, we first use this result for a double chain on kpoints (k/2 points on each chain), obtaining Ω(4.64k) different k-polygonizations. Then we distribute the remaining n−kpoints among all possible positions, meaning that for each k-polygonization, we obtain the double chain on npoints with a k-hole drawn; see Figure 3. In their proof, Garc´ıa et al. count paths that start at the first vertex of the upper chain and end at the last vertex of the lower chain. Before the first vertex on the lower chain, they add an additional point qto complete these paths to polygonizations. We slightly extend this principle, by also adding an additional point pon the upper chain after the last vertex; see Figure 2. Then we complete each path Cto a polygonization in one of the following ways: Either we add pto Cdirectly next to pk 2−1and then complete Cvia q, obtaining Pq, or we add qto Cdirectly next to q1, and close the polygonization via p, obtaining Pp; see again Figure 3. 7 p1p pk 2−1 qk 2−1 q1 q C p2 q2 Figure 2: A path Cin the double chain, using all but the vertices pand q. p1p pk 2−1 qk 2−1 q1 q Pp p2 q2 p1p pk 2−1 qk 2−1 q1 q Pq p2 q2 Figure 3: Two ways to complete a path to a polygonization. Note that this changes the number of polygonizations only by a constant factor and thus does not influence the asymptotic bound. However, the interior of Pqis the exterior of its “complemented” polygonization Pp, meaning that if we place a point somewhere on the double chain and it lies inside Pq, then it lies outside Pp, and vice versa. It follows that, in one of the two polygonizations, at least half of the k+ 2 positions to insert points are outside the polygonization. Hence, we can distribute the n−k 2 points on each chain to at least k 2+ 1 possible positions in total. Now, on one of the two chains we have at least k 4+ 1 positions; see again Figure 3. More precisely, there are k 4+j+ 1 positions on this chain (where 0 ≤j < k 4) and (at least) max{2,k 4−j}positions on the other chain. The lower bound stems from the fact that the positions before the first and after the last vertex of a chain are always possible. Placing apoints on the bpositions of one chain can be seen as placing aballs into bboxes. The number of ways to do so is a+b−1 a. Using this, we obtain n−k 2+k 4+j n−k 2·max (n−k 2+1 n−k 2,n−k 2+k 4−j−1 n−k 2) possibilities to place the remaining points on the two chains. This factor is minimized for j=k 4−2, which yields the claimed lower bound of n−4 2 n−k 2·n−k+ 2 2·Ω(4.64k) for the number of k-holes of DC(n). 4 An upper bound for the number of non-convex k-holes The following theorem shows that for sufficiently small kwith respect to n, the maximum number of non-convex k-holes is smaller than the maximum number of convex k-holes. Theorem 7. For any constant k≥4, the number of non-convex k-holes in a set of npoints is bounded by O(nk−1)and there exist sets with Ω(nk−1)non-convex k-holes. 8 Proof. We first show that there are at most O(nk−1) non-convex k-holes by giving an algorithmic approach to generate all non-convex k-holes. We represent a non-convex k-hole by the counter-clockwise sequence of its vertices, where we require that the last vertex is reflex and its removal results in a simple (k−1)-gon; see again the proof of Theorem 5. Any non-convex k-hole has r≥1 such representations, where ris at most the number of its reflex vertices. Thus the number of different representations is an upper bound on the number of non-convex k-holes. For 1 ≤i≤k−1, we have n−i+1 possibilities to choose the i-th vertex vi. If the resulting (k−1)-gon is non-simple, we ignore it (but still count it). For the last vertex vk, we have at most one possibility: As vkis required to be reflex and the polygon has to be empty, we have to use the inner geodesic connecting vk−1back to v1. Only if this geodesic contains exactly one point, namely vk, we do obtain one nonconvex k-hole. Altogether, we obtain at most n(n−1)(n−2) . . . (n−k+ 2) = n!/(n−k+1)! = O(nk−1) non-convex k-holes. Figure 4: A set with Θ(nk−1) non-convex k-holes. For an example achieving this bound see Figure 4. Each of the four indicated groups of points contains a linear fraction of the point set; for example n 4points. To show that in this example we have Ω(nk−1) non-convex k-holes it is sufficient to only consider the k-holes with triangular convex hull of the type indicated in the figure. For each of the three vertices of the convex hull of the k-hole we have a linear number of possible choices, and the k−4 non-reflex inner vertices can also be chosen from a linear number of vertices. Hence, we obtain Ω n3·n k−4= Ω(nk−1) non-convex k-holes. 5 On the minimum number of (general) k-holes We start with an upper bound on the minimum (over all n-point sets) number of (general) k-holes. Note that the minimum number of (general) k-holes cannot be greater than the minimum number of convex k-holes plus the maximum number of non-convex k-holes. Recall that the minimum number of convex k-holes is O(n2) for k≤6 (and zero for k≥7), and the maximum number of non-convex k-holes is O(nk−1). For k≥3, the latter dominates the former, yielding an upper bound of O(nk−1) for the minimum number of general k-holes. But this bound is by far not tight, as the following considerations show. 5.1 An upper bound on the minimum number of (general) k-holes using grids Consider an integer grid Gof size √n×√n. We denote a segment spanned by two points of Gthat does not have any points of Gin its interior as prime segment. Further, we denote the slope of a line lspanned by points of Gas the differences (dx, dy) of the coordinates of the endpoints of a prime segment on l. Note that a line with slope (0,1) or (1,0) contains exactly √npoints of G. A line with slope (dx, dy), both dx, dy6= 0, contains at most min nl√n |dx|m,l√n |dy|mopoints of G. A k-gon spanned by points of Gis called interior-empty if it does not contain any points of Gin its interior. Lemma 8. In an integer grid Gof size √n×√n, every segment is incident to at most O(√nlog n) interior-empty triangles. 9 [30] J. Kalbfleisch, J. Kalbfleisch, and R. Stanton. A combinatorial problem on convex n-gons. In Proc. Louisiana Conference on Combinatorics, Graph Theory and Computing, 1970, pages 180–188, Louisiana State University. [31] V. A. Koshelev. On Erd˝os–Szekeres problem for empty hexagons in the plane. Model. Anal. Inform. Sist, 16(2):22–74, 2009. In Russian. [32] J. A. D. Loera, J. Rambau, and F. Santos. Triangulations: Structures for Algorithms and Applications, volume 25 of Algorithms and Computation in Mathematics. Springer-Verlag, 2010. [33] C. Nicol´as. The empty hexagon theorem. Disc. Comp. Geom., 38(2):389–397, 2007. [34] R. Pinchasi, R. Radoiˇci´c, and M. Sharir. On empty convex polygons in a planar point set. J. Comb. Theory Ser. A, 113:385–419, April 2006. [35] M. Sharir, A. Sheffer, and E. Welzl. Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn’s technique. J. Comb. Theory Ser. A, 120:777–794, 2013. [36] G. Szekeres and L. Peters. Computer solution to the 17-point Erd˝os–Szekeres problem. The ANZIAM Journal, 48(2):151–164, 2006. [37] G. T´oth and P. Valtr. The Erd˝os–Szekeres theorem: upper bounds and related results. Combinatorial and Computational Geometry, J.E. Goodman, J. Pach, and E. Welzl (Eds.),, 52:557–568, 2005. [38] P. Valtr. Convex independent sets and 7-holes in restricted planar point sets. Disc. Comp. Geom., 7:135–152, 1992. [39] P. Valtr. On the minimum number of empty polygons in planar point sets. Studia Scientiarum Mathematicarum Hungarica, 30:155–163, 1995. [40] P. Valtr. On empty hexagons. J. E. Goodman, J. Pach, and R. Pollack, Surveys on Disc. Comp. Geom., Twenty Years Later, Contemp. Math. 453, AMS, 453:433–441, 2008. [41] P. Valtr. On empty pentagons and hexagons in planar point sets. In Proc. CATS2012, pages 47–48, Melbourne, Australia, 2012. [42] B. Vogtenhuber. Combinatorial Aspects of [Colored] Point Sets in the Plane. PhD thesis, Institute for Software Technology, Graz University of Technology, Graz, Austria, 2011. 16