On polygons enclosing point sets II

On polygons enclosing point sets II F. Hurtado1, C. Merino2, D. Oliveros3, T. Sakai4, J. Urrutia5, I. Ventura6∗ 1Departament de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya. 2Instituto de Matem´aticas, Universidad Nacional Aut´onoma de M´exico, M´exico D.F. M´exico. 3Instituto de Matem´aticas, Universidad Nacional Aut´onoma de M´exico, M´exico D.F. M´exico. 4Research Institute of Educational Development, Tokai University, 2-28-4 Tomigaya, Shibuyaku, Tokyo 151-8677, Japan 5Instituto de Matem´aticas, Universidad Nacional Aut´onoma de M´exico, M´exico D.F. M´exico. 6Departmento de Matem´aticas, Universidad de Huelva, Huelva, Espa˜na. Abstract. Let Rand Bbe disjoint point sets such that R∪Bis in general position. We say that Bencloses by Rif there is a simple polygon Pwith vertex set Bsuch that all the elements in Rbelong to the interior of P. In this paper we prove that if the vertices of the convex hull of R∪Bbelong to B, and |R| ≤ |Conv(B)| − 1 then Bencloses R. The bound is tight. This improves on results of a previous paper in which it was proved that if |R| ≤ 56|Conv(B)|then Bencloses R. To obtain our result we prove the next result which is interesting on its own right: Let Pbe a convex polygon with nvertices p1,...,pnand Sa set of mpoints contained in the interior of P, m≤n−1. Then there is a convex decomposition {P1,...,Pn}of Psuch that all points from S lie on the boundaries of P1,...,Pn, and each Picontains a whole edge of Pon its boundary. Key words. Enclosing polygon, red blue point sets. 1. Introduction Let Sbe a set of npoints in the plane in general position. A polygonization of Sis a simple polygon such that its vertex set is S. Finding an upper and lower bounds on the number of polygonizations any point set admits is a problem that has been receiving much attention since it was posed in 1979 by Akl [2] and 1980 by Newborn and Moser [13]. In [2] a lower bound of 2.27nwas proved. An upper bound of the form cnfor some constant c(ignoring polynomial terms) was conjectured by Newborn and Moser [13]. This was proved in 1982 by Ajtai, Chv´atal, Newborn, and Szemer´edi [1], who proved that there are at most 1013ncrossing-free graphs on npoints in a paper that had strong influence in the latter theory of geometric graphs [3]. This bound has been improved in several papers, and most recently for polygonizations to 86.81nby Sharir and Welzl [15]. Any simple polygon Pdefines two open regions on the plane, a bounded one called the interior of Pand an unbounded region called the exterior of P. The area of Pis the ∗F. Hurtado partially supported by projects MEC MTM2006-01267 and DURSI 2005SGR00692. C. Merino supported by CONACYT of Mexico, Proyecto 43098. J. Urrutia supported by CONACYT of Mexico, Proyecto SEP-2004-Co1-45876, and MCYT BFM2003-04062. I. Ventura partially supported by Project MCYT BFM2003-04062. 2 F. Hurtado et al. area of the region bounded by P. Problems of finding polygonizations of point sets Sthat maximize or minimize some parameters of the polygonization have also been studied. S. Fekete [9] considers the problem of finding polygonizations of point sets Sthat minimize or maximize the enclosed area. He proves that finding such polygonizations is NPcomplete. It is worth mentioning here that a tool used by Fekete, is Pick’s Theorem, a classic result on polygonizations that for polygons with vertices on the integer lattice, establishes an elegant relation between the area of the polygons and the number of lattice points on the boundary and in the interior of such polygons [14,4]. The problem of finding polygonizations of point sets that minimize the perimeter is the famous Euclidean Travelling Salesman problem, and it is well known that this problem is NP-hard [11]. Fig. 1. The polygon through the points represented by small solid points encloses all of the points represented by small empty circles. We say that a polygon Pencloses a point set Sif all the elements of Sbelong to the interior of P; see Figure 1. Let Rand Bbe disjoint point sets on the plane such that S=R∪Bis in general position. The elements of R(respectively B) will be called the red points of S(respectively the blue points of S). A polygonization of Bwill be called a blue polygonization. The problem of finding a blue polygonization that encloses as many red points as possible was studied in [5]. Since any red element of Sthat is enclosed by a blue polygonization must belong to the interior of the convex hull Conv(B) of B, in what follows we will assume that all the elements of Rbelong to the interior of Conv(B). Under this assumption, it is proved in [5] that there always exists a blue polygonization that encloses at least half of the elements of R. Moreover this bound is asymptotically tight. It is also proved that there always exists a polygon that covers at least half of the area of the convex hull of S. Let kdenote the number of vertices on Conv(B), and ithe number of elements of B in the interior of Conv(B), i+k=n. In [5] it was also proved that if |R| ≤ 56k, then there always exists a blue polygonization that encloses R. It is easy to see that there are red point sets contained in Conv(B) with kelements such that the whole of Rcannot be enclosed by any blue polygonization; simply let Rhave an element close enough to the midpoint of each of the kedges of Conv(B), and make sure that Bhas at least one point in the interior of Conv(B) as shown in Figure 2. Our main goal in this paper is to show that if Rhas at most k−1 points, then there always exists a blue polygonization that encloses R. The main tool used here is a partitioning lemma that we consider to be of interest on its own, asserting the following: Let Pbe a convex polygon with nvertices, and Sa point set contained in Pwith at most n−1 elements. Then there is a set of nconvex polygons P1,...,Pnwith disjoint interiors On polygons enclosing point sets II 3 Fig. 2. The blue points are represented by small solid circles, the red ones by small empty circles. such that the elements of Sbelong to the boundaries of P1,...,Pn, each Picontains on its boundary exactly one edge of P, and P1∪...∪Pn=P. See Figure 3. Fig. 3. The Decomposition Lemma. We conclude this paper showing how to construct blue and red point sets with n=i+k and m=k−2 + 2ielements respectively, such that any blue polygon contains exactly n−2 red points. Observe that when k= 3, Rhas exactly m= 2n−5 elements, and thus any blue polygonization contains exactly m+1 2red points in its interior and m−1 2points in its exterior. 2. The Decomposition Lemma Let Pbe a convex polygon with nvertices. We call a set of convex polygons {P1,...,Pn} with disjoint interiors a convex decomposition of Pif it satisfies the following conditions: –P1∪...∪Pn=P –Each Pihas exactly one edge of Pon its boundary, called the lid of Pi. P1,...,Pnwill be called the pockets of the decomposition. See Figure 3. In the rest of this paper, all point sets or unions of point sets will be assumed to be in general position. If the vertices of a polygon Pare labelled p1,...,pnin the counter-clockwise order along its boundary, we might refer to Pas to the polygon p1p2. . . pnp1. In this section we prove: Theorem 1. [Decomposition lemma] Let Pbe a convex polygon with nvertices p1,...,pn and Sa set of mpoints contained in the interior of P,m≤n−1. Then there is a convex decomposition {P1,...,Pn}of Psuch that all the points of Slie on the boundaries of P1,...,Pn, see Figure 3. 4 F. Hurtado et al. We present some preliminary results that will be useful to prove Theorem 1. Lemma 1. Let Tbe a triangle with vertices p1,p2and p3, that contains in its interior a set Sof 2 + x1+x2points, where x1and x2are any non-negative integers. Then, there is a point tin the interior of Tsuch that one of the following situations happens: (a) The union of the segments tp1,tp2and tp3covers exactly two points from S, and there are x1and x2points from Sin the interior of the triangles tp1p2and tp2p3, respectively. (b) Each one of the segments tp1,tp2and tp3covers exactly one point from S, and there are x1−1and x2points from Sin the interior of the triangles tp1p2and tp2p3, respectively. (c) Each one of the segments tp1,tp2and tp3covers exactly one point from S, and there are x1and x2−1points from Sin the interior of the triangles tp1p2and tp2p3, respectively. Proof. Let t0be a point on the segment p1p3such that the triangles t0p1p2and t0p2p3 have, respectively, x1+ 1 and x2+ 1 points from Sin their interior (Figure 4, left). 0 x +1 x +1 0 1 1 2 2 3 t pp p 0 1 x 1 2 x 2 3 t pp p t Fig. 4. Decomposing a triangle: first step. We consider a point tthat moves along the segment t0p2, with initial position t=t0, until some point from Sis encountered by one or both of the segments tp1and tp3. If two points are simultaneously found, one by tp1and the other by tp3we are in situation (a). Our result follows, see Figure 4, right. Suppose then that a point q1from Sis intersected by the segment p1t(the case q1∈ p3tis identical). Let t1be the intersection point of the lines generated by p1tand p2p3 (Figure 5, left); now we move the point ttowards t1along the line segment p1t1. If one point from Sis met by either of tp3or tp2we are again in case (a) and we are done (Figure 5, center). If two points are simultaneously met by tp3and tp2, we are in situation (c) (Figure 5, right). t t t  x +1 x 00 0 0 1 1 2 2 3 t1 t pp p  1 x 1 2 x 2 3  pp p x -1 1 x 1 2 2 3 pp p Fig. 5. Decomposing a triangle: second step. On polygons enclosing point sets II 5 Proof of Theorem 1 Observe that we can assume that m=n−1, for otherwise we can add (n−1)−mdummy points to the set S, obtain a convex partition, and then remove the dummy points. We prove our result by induction on n; the base case n= 3 follows from Lemma 1 with x1=x2= 0. Suppose that the vertices of Pare labeled p1,...,pnin the counter-clockise direction along its boundary such that the lower vertex of Pis precisely pn, and pnlies on the origin, (refer to Figure 6). Every point qcan be described by its polar coordinates (r(q), ϕ(q)), where r(q) is the distance from qto the origin and ϕ(q) is the angle from the positive axis +xto the ray through qwith apex at the origin. p1 p2 pn-1 pnr Fig. 6. Choice of the reference. For every value αin the interval [0, π] we define a function gas follows: g(α) = |{q∈S|ϕ(q)< α}| − |{pi|ϕ(pi)< α, 1≤i < n}|. Therefore, in particular, g(ϕ(p1)) =0 −0 = 0; g(ϕ(pn−1)) =(n−1) −(n−2) = 1; g(ϕ(pi)) =|{q∈S|qis in the interior of the polygon with vertices pn, p1,...,pi}| − (i−1). Let jbe the smallest index such that j > 1 and g(ϕ(pj)) ≥0; such an index must exist because g(ϕ(pn−1)) = 1. Several cases arise. Case 1:g(ϕ(pj)) = 0. In this case the number of points from Sinside the polygon pnp1. . . pjpnis exactly j−1 and we have g(ϕ(pi)) <0 for all the values of isuch that 1< i < j, see Figure 7. The polygon b P=pnpjpj+1 . . . pn−1pnhas n−j+ 1 vertices; let b Sbe the set of points of Sthat are interior to b P. Since | b S|= (n−1) −(j−1) = n−j < n −1, we can apply induction to the polygon b Pand the point set b Sand obtain a convex partitioning Πof b P; let Q∈Πbe the pocket of b Pwhose lid is pnpj. Let Qj−1be the convex polygon obtained by the union of polygons Qand pnp1p2. . . pjpn; note that Qj−1contains exactly j−1 points from S, namely the set Sj−1=S\ b S. 6 F. Hurtado et al. p1 pj-1 pj-2 Qj-1 pj p2 pn-1 pn Fig. 7. First step in Case 1. Let us consider a moving point tthat travels counterclockwise on the boundary of Qj−1, starting at pj. Before treaches pnsome point q∈Smust be met by the segment pj−1t, otherwise we would have j−1 points of Sinside pnp1. . . pj−1pnand then g(ϕ(pj−1)) >0, contradicting the choice of j. We add the chord of Qj−1through pj−1and qto the decomposition of Pthat we are constructing and remove from Qj−1the region swept by pj−1tuntil qwas found; in this way we obtain a new convex polygon Qj−2that contains exactly j−2 points from Sin its interior, namely the set Sj−2=Sj−1\ {q}(Figure 8, left ). We repeat the preceding construction by sweeping with a chord of Qj−2having one endpoint anchored at pj−2and so on, until the claimed decomposition of Pis completed (Figure 8, right). p 1 p j-1 p j-2 p j p 2 p n-1 p n p 1 p j-1 p j-2 p j p 2 p n-1 p n q Q j-2 Fig. 8. Iterative step and final construction for Case 1. Case 2:g(ϕ(pj)) >0. In this case the number of points from Sinside the polygon pnp1. . . pjpnis at least jand we have g(ϕ(pi)) <0 for all the values of isuch that 1< i < j. Let y1and y2be the number of points of Sin the interior of the polygons pnp1p2. . . pj−1pn and pnpjpj+1 . . . pn−1pn, respectively. From the preceding observations we see that y1≤ j−2 and that (n−1) −y2≥j; i.e., y2≤n−1−j. If we define the numbers x1=j−2−y1, x2=n−1−j−y2, On polygons enclosing point sets II 7 we see that the number xof points from Sinterior to the triangle pnpj−1pjis x= (n−1) −(y1+y2) = (n−1) + (x1−j+ 2) + (x2−n+ 1 + j) = x1+x2+ 2 ≥2. p1 pj-1 pj+1 pj-2 Qj-2 Qj+1 pj p2 pn-1 pn q Fig. 9. First step for Case 2. Therefore, we can apply Lemma 1 to the triangle with the numbers x1and x2associated to the sides pnpj−1and pnpj, respectively. Let qbe the point such that the segments qpn, qpj−1and qpjsplits triangle pnpj−1pjas in Lemma 1. Let Qj−2be the convex polygon obtained as union of the triangle pnpj−1qand the polygon pnp1p2. . . pj−1pn; let Qj+1 be the convex polygon obtained as union of the triangle pnqpjand the polygon pnpjpj+1 . . . pn−1pn(Figure 9). Three subcases arise, that we describe separately; in all of them the segments qpn,qpj−1and qpjare used for the decomposition of P. Subcase 2.1: The union of the segments qpn,qpj−1and qpjcovers two points from Sand triangles qpnpj−1and qpjpncontain x1and x2points from S, respectively, in their interior. Let Sj−2and Sj+1 be the set of points interior to Qj−2and Qj+1, respectively. We have |Sj−2|=x1+y1=j−2 and |Sj+1|=x2+y2=n−1−j(Figure 10, left). p 1 pj+1 p j-2 pj-1 pj-1 pj p2 pn-1 pn q Qj+1 Qj-2 y 1 x 1 x2 y2 p 1 pj+1 p j-2 pj p2 pn-1 pn q Qj+1 x2 y2 Fig. 10. Initial situation in Subcase 2.1 and decomposition of Qj−2. For the decomposition of Qj−2we consider a segment with one endpoint at pj−2and the other one at a moving point tthat travels counterclockwise on the boundary of Qj−2, 8 F. Hurtado et al. with starting position t=pj−1; a point from Smust be found by the sweeping chord before treaches pn, and we proceed as in the proof of Case 1 achieving the decomposition of Qj−2(Figure 10, right). For the decomposition of Qj+1 we consider a segment with one endpoint at pj+1 and the other one at a moving point tthat travels clockwise on the boundary of Qj+1, with starting position t=pj. If some point of Sj+1 is found before treaches pn, we cut off the swept area and iterate as in the previous situation; if this keeps happening we arrive at the decomposition of Figure 11, left. p 1 pj+1 p j-2 pj p2 pn-1 pn q p 1 pj+1 p j-2 pj p2 pn-1 pn q pj-1 pj-1 Fig. 11. Decomposition of Qj+1 in Subcase 2.1. If treaches pnand no point from Sj+1 has been encountered, all points from Sj+1 must lie in the interior of the polygon b P=pnpj+1pj+2 . . . pn−1pn; this polygon has n−j= |Sj+1|+ 1 vertices and hence we can apply induction to b Pand Sj+1. In the final step, we obtain the overall decomposition of Pby considering the pocket (with lid the edge pjpj+1) formed by the union of the triangles pnqpjand pjpj+1pn, together with the pocket corresponding to pnpj+1 in the decomposition of b P(Figure 11, right). p 1 pj+1 p j-2 pj-1 pj p2 pn-1 pn q Sj+1 Sj-2 p 1 pj+1 p j-2 pj-1 pj p2 pn-1 pn q Sj+1 Sj-2 Fig. 12. Subcases 2.2 and 2.3. Subcase 2.2: Each one of the segments qpn,qpj−1and qpjcovers one point from Sand the interior of the triangles qpnpj−1and qpjpncontain, respectively, x1−1 and x2points from S. Let Sj−2be the set of points of Sinterior to Qj−2together with the point from Scovered by the segment qpn, and let Sj+1 be the set of points of Sinterior to Qj+1 (Figure 12, left). We again have |Sj−2|= (x1−1) + y1+ 1 = j−2 and |Sj+1|=x2+y2=n−1−j and continue with the sets Sj−2and Sj+1 as in Subcase 2.1 . On polygons enclosing point sets II 9 Subcase 2.3: Each one of the segments qpn,qpj−1and qpjcovers one point from Sand the interior of the triangles qpnpj−1and qpjpncontain, respectively, x1and x2−1 points from S. Let Sj−2be the set of points of Sinterior to Qj−2and let Sj+1 be the set of points of Sinterior to Qj+1 together with the point from Scovered by the segment qpn(Figure 12, right). We again have |Sj−2|=x1+y1=j−2 and |Sj+1|= (x2−1) + y2+ 1 = n−1−j and continue with the sets Sj−2and Sj+1 as in Subcase 2.1. 3. Main Result We recall an observation made in [5]. Observation 1 Let Pbe a convex polygon, pipjan edge of P, and Sa set of points in the interior of P. Then there is a simple polygonal starting at piand ending at pjsuch that its vertex set is {pi, pj} ∪ S, see Figure 13. p i p j p i p j Fig. 13. The polygonal within a pocket. We can now prove: Theorem 2. Let Rand Bbe two point sets such that S=R∪Bis in general position and Ris contained in the interior of Conv(S). Then, if the number of vertices of Conv(S) is kand |R|< k, there is a blue polygon enclosing all points of R. This result is tight. Proof. The fact that |R|is less than kfollows from the example depicted in Figure 2. By Theorem 1, we can obtain a convex decomposition {P1,...,Pk}of Conv(B) such that all the points in Rbelong to the boundaries of P1,...,Pk. By the previous observation, in each Piwe can find a polygonal contained in Pi, that starts and ends at the vertices of Pi in Conv(B) and contains only all the elements of Bin the interior of Pi. Concatenate the polygonal chains thus obtained. It is clear that this way we obtain a blue polygon that encloses all the elements of R, see Figure 14. 4. Revisiting Enclosed Point Sets and Areas It was proved in [5] that given S=R∪Bas before, there always exists a blue polygonization that encloses at least half of the elements of R, and that this value is essentially