Monochromatic geometric k-factors for bicolored point sets with auxiliary points

Information Processing Letters Monochromatic geometric k-factors for bicolored point sets with auxiliary points ✩ D. Garijo ∗, M.A. Garrido, C.I. Grima, A. Márquez, A. Moreno-González, J.R. Portillo, P. Reyes, R. Robles, J. Valenzuela Department of Applied Mathematics I, University of Seville, Spain abstract Keywords: Computational geometry Red–blue point sets k-factors Steiner points Given a bicolored point set S, it is not always possible to construct a monochromatic geometric planar k-factor of S. We consider the problem of finding such a k-factor of S by using auxiliary points. Two types are considered: white points whose position is fixed, and Steiner points which have no fixed position. Our approach provides algorithms for constructing those k-factors, and gives bounds on the number of auxiliary points needed to draw a monochromatic geometric planar k-factor of S. 1. Introduction Let Sbe a set of npoints in the plane such that each point is colored red or blue. Let Rbe the set of red points and Bthe set of blue points. Assume that the points of S are in general position, that is, no three of them lie in the same line. We say that a planar k-regular graph is a planar k-factor of SifitsverticesarethepointsofS.Iftheedges are straight-line segments then we have a geometric planar k-factor of S. Observe that a geometric perfect matching of Sis a geometric planar 1-factor. Note also that since no 6-regular graph is planar, then geometric planar k-factors can only exist for 1 ⩽k⩽5. A geometric planar k-factor of S=R∪Bis monochromatic if its edges join points of the same color. For simplicity, we shall write k-factor instead ✩A preliminary version of this paper appeared in [6]. *Corresponding author. E-mail addresses: dgari[email protected] (D. Garijo), [email protected] of monochromatic geometric planar k-factor when no confusion can arise. This paper addresses a general study of monochromatic geometric planar k-factors, which as far as we know have not been yet studied for k>1. Indeed, only the case k=1 has been considered in the literature (see [4]). Since it is easy to give configurations of red and blue points for which it is not possible to construct a 1-factor (and in general, a k-factor), then the problem in this case turns to find a largest non-crossing geometric matching of pairs of points of the same color (see [1] for a recent paper). Dumitrescu and Kaye [4] provided an O(n2)-time algorithm that computes a matching of at least 85.71% of the points. Within this context, it seems natural to ask whether the situation can be modified by using auxiliary points, that is, points that do not belong to S. In this paper, we consider two types of auxiliary points: (1) white points, which are given as part of the input, their position is fixed; (2) Steiner points, which have no fixed position and they are inserted only when they have to be used, not being part of the input. Both Steiner and white points have no color assigned until they are matched with a red or blue point, inheriting its color. (M.A. Garrido), [email protected] (C.I. Grima), [email protected] (A. Márquez), [email protected] (A. Moreno-González), joser[email protected] (J.R. Portillo), prey[email protected] (P. Reyes), [email protected] (R. Robles), [email protected] (J. Valenzuela). 20 D. Garijo et al. / Information Processing Letters 114 (2014) 19–24 Once we have studied the case k=1, we go further providing a first approach to the problem of computing monochromatic geometric planar k-factors with 2 ⩽k⩽5, for bicolored point sets, also using both types of auxiliary points. Our main goal is to minimize the number of auxiliary points, and in case of combining both types we shall give preference to white points since, unlike Steiner points, they are part of the input and the use of all of them is not necessary to construct a k-factor. As an analogy, suppose that the red and blue data are two types of installations that have to be joined giving rise to a k-factor. White points play the role of installations already constructed which can easily be adapted to a red or blue use, and Steiner points correspond to new installations that have to be built. From this point of view, Steiner points are much more expensive than white ones, and they should be avoided if it is possible. Steiner points have been used in several problems in computational geometry [5,7], but white points have not been considered in general (see [12] where they are called Steiner points with fixed position). Note that if no restriction is imposed on the number of Steiner points, it suffices to add a large enough number around every point of Sto construct a k-factor. Nevertheless, we prove that there are configurations of points that do not admit a planar k-factor independently of the number of white points used. In all the figures, red, blue, and white points are depicted as black, gray, and white points, respectively; Steiner points are represented by squares. 2. Monochromatic perfect matchings (1-factors) Given a bicolored point set S, it is not always possible to obtain a monochromatic perfect matching of S,soitis necessary to use auxiliary points; either Steiner points, or white points, or both. The aim of this section is to provide bounds on the number of auxiliary points that are sufficient to guarantee the existence of a perfect matching of S. A key result within this context is the following theorem. Theorem 2.1. (See [4,9].) (i) There exists a monochromatic matching which covers at least 6 7n+O(1)points of S =R∪B, and such a matching can be found in O(n2)time. (ii) There exists a point configuration R ∪Bforwhichevery monochromatic geometric matching covers at most 94 95 n+ O(1)points. Remark 2.2. The O(n2)-time algorithm provided in [4] can be slightly modified in order to obtain a monochromatic perfect matching of S, by adding a Steiner point close to every point of Sthat has not been matched. Thus, n/7 Steiner points suffice to construct the matching. This modified process will be called Steiner-Matching. We now recall a result that plays an important role throughout this paper. Fig. 1. Any segment joining a pair of, say, red points isolates an odd number of colored points and so n−1 white points do not suffice to obtain a monochromatic perfect matching. Theorem 2.3 (Equitable Subdivision Theorem). (See [2,8,11].) Given integers a ⩾1,b⩾1and g ⩾2, if R contains ag red points and B contains bg blue points, then there exists a subdivision X1∪X2∪···∪ Xgof the plane into g disjoint convex polygons such that every Xicontains exactly a red points and b blue points. An equitable subdivision of the plane can be found in O(n4/3log3nlog g)time [2], where n=(a+b)g.Consider now a set of nwhite points, a set of ncolored points (red plus blue), and take a=1, b=1 and g=n. By Theorem 2.3 (where Rand Bare the sets of nwhite points and ncolored points, respectively) there are only one white point and one colored point inside every convex polygon. These points can be matched giving rise to a planar monochromatic matching, once the white points take the proper color. This procedure will be called Bichro- Matching.Moreover,Fig. 1 illustrates a configuration of points that requires to add nwhite points to obtain a monochromatic perfect matching. This implies the following theorem. Theorem 2.4. Let S=R∪B. A set of n white points are always sufficient and sometimes necessary to obtain a monochromatic perfect matching of S, which can be found in O (n4/3log4n) time. A way of constructing a perfect matching when there are fewer than nwhite points is to add Steiner points. This can be done as follows. Let Swbe a set of nred and blue points and n−m white points, and consider its convex hull CH(Sw)= {p0,...,ph}sorted clockwise. First, check whether there exist two consecutive points pi,pi+1∈CH(Sw), either with the same color or a colored point and a white point. If so, match them, update CH(Sw)to CH(Sw\{pi,pi+1}), and search for another pair. Once all pairs pi,pi+1have been matched, we obtain a set S wthat contains the remaining ncolored points and swhite points, and such that CH(S w)has only white points or consists of alternating red and blue points (note that it might be Sw=S w). Now, if CH(S w)has only white points, rotate clockwise a line anchored on a point p i∈CH(S w)starting at p i+1in order to compute a set Dwith the same number of white and colored points. Observe that if s>n,oursetDmight not exist: there could be a set containing the ncolored points and a number >nof white points; to obtain D it suffices to color an adequate number of white points. D. Garijo et al. / Information Processing Letters 114 (2014) 19–24 21 Then, procedure Bichro-Matching gives a matching of D. Finally, update CH(S w)by removing the set D. When CH(S w)consists of alternating red and blue points, rotate clockwise the line anchored on p istarting at p i+1until finding a point q∈S w.Ifqand p i+1have the same color or qis white, match them and update CH(S w)to CH(S w\{p i+1,q}).Otherwise,qis matched with p iand p i+1with a Steiner point; update CH(S w)to CH(S w\{p i,p i+1,q}). The process concludes when either there are no white points left and we can apply procedure Steiner-Matching (here we include the case in which there are only white points left; they can simply be colored), or there is the same number of white and colored points and procedure Bichro-Matching can be applied. The above described procedure, called White-Steiner- Matching, implies the following theorem. Theorem 2.5. Given a set S =R∪B of n colored points, and a set of n −m white points, at most m/3Steiner points suffice to obtain a monochromatic perfect matching of S. It is possible to construct such a matching in O(m2)+O(n4 3log4n)time. Proof. Consider the set Swthat is the union of Sand the n−mwhite points. By Remark 2.2 and Theorem 2.4,procedure White-Steiner-Matching gives a monochromatic perfect matching of Susing white and Steiner points. Observe that at each step, any matched pair can be separated from the remaining points of Swby a line, avoiding crossings with the segments added in the next steps of the process. After removing all pairs pi,pi+1from CH(Sw)and obtained the set S w, Steiner points are used in two situations: either CH(S w)consists of alternating red and blue points, or there are no white points left. In the former case, each Steiner point is used to match three colored points. Since n−mcolored points are matched using white points, then m/3 Steiner points might be needed. In the latter case, the process calls procedure Steiner-Matching, using one Steiner point for every seven colored points. Analysis of procedure White-Steiner-Matching:theprocess searches through the convex hull for a suitable pair, matches, removes it from CH(Sw), and updates the convex hull. Updating CH(Sw)can be done in O(logn)time [3].IfCH (Sw)has only white points, the process calls procedure Bichro-Matching on subsets Diof nipoints, and ini⩽2n.ByTheorem 2.4, this can be done in iO(n4/3 ilog4ni)which is O(n4/3log4n). Finally, procedure Steiner-Matching is applied at most once and takes O(m2)time. 2 3. Monochromatic k-factors In light of the previous discussion, we now provide a firstapproachtotheproblemoffindingak-factor, 2 ⩽ k⩽5, using auxiliary points. The main tool to construct k-factors (for every k) using Steiner points is given by the following theorem. Theorem 3.1. Let S=R∪B. It is possible to construct two monochromatic non-crossing Hamiltonian cycles on R and B, Fig. 2. (a) Polygons PRand RB, (b) cycles CRand CB. respectively, in O(nlogn)time using at most n 2Steiner points. Moreover, the bound on the number of Steiner points is tight. Proof. If the given sets Rand Bof red and blue points are line separable, then it is trivial to obtain two monochromatic cycles. Otherwise, we proceed as follows: Find a point p∈CH(R)∩CH(B)and let PR(resp. PB)bethe polygon resulting from joining the points of R(resp. B) following the angular order given from p(see Fig. 2(a)). Denote by IROBthesetofbluepointsinsidePRplus the redpointsoutsidePB. Analogously, let IBORbe the set of red points inside PBplus the blue points outside PR. Consider now the polar coordinate system centered at p.I f|IBOR|⩽|IROB|(analogous for |IROB|⩽|IBOR|), then for every blue point b=(θ, ρ)(θbeing the angle and ρthe distance from p)inIBORadd a red Steiner point sr=(θ, ρ+ε), and for every red point r=(θ,ρ)in IBOR add a blue Steiner point sb=(θ,ρ−ε). Joining the red points and the blue points in the angular order from p,we obtain two monochromatic non-crossing cycles CRand CB (Fig. 2(b)). This procedure will be called Steiner-cycles. Since IROBand IBORare disjoint and |IROB∪IB OR|=n,atmostn 2Steiner points are needed to construct CRand CB. We now prove that the bound is tight. To do this, we show that a set S=R∪Bof nalternating red and blue points in convex position always uses at least n 2 Steiner points. Since the two monochromatic non-crossing cycles can always be constructed using at most n 2Steiner points, then the result follows. Let CBbe a non-crossing Hamiltonian cycle on B. Clearly, every edge eof CBsplits the set Rinto two independent subsets, i.e., it is not possible to match two red points located on opposite sides of e. Thus, at least one Steiner point is required to connect both subsets in order to construct a monochromatic Hamiltonian cycle CRon R. Note that since every point in the resulting graph must have degree two, each Steiner point can be used to join only two such subsets. Now, take an edge bibi+1∈E(CB)and assume bi∈B. Then, the point bi+1is either a Steiner point or belongs to B. The latter case implies, by the argument above, the use of at least one red Steiner point to construct CR.Therefore, we are using at least one Steiner point (either red or blue) per each edge of CBwhich implies at least n 2 Steiner points in total. Procedure Steiner-cycles takes O(n)time to check whether Rand Bare line separable [10]. Then, it computes the convex hulls and sorts the points to construct PRand PBin O(nlogn)time. Also, in O(nlogn)time, the 22 D. Garijo et al. / Information Processing Letters 114 (2014) 19–24 procedure determines the blue (resp. red) points that are exterior and interior to PR(res. PB). Finally, it traverses both polygons adding Steiner points obtaining CRand CB in O(n)time. 2 The output of procedure Steiner-cycles is a 2-factor of Sconsisting of two monochromatic non-crossing cycles containing at most n 2Steiner points. Nevertheless, it is possible to reduce the number of Steiner points used by decreasing the connectivity of the resulting graph. This can be done as follows. Split Sinto subsets of mpoints, for modd and 5 ⩽ m<n,sortingbyx-coordinate (assuming without loss of generality, that no two points have the same x-coordinate) and apply procedure Steiner-cycles to each group. Since consecutive subsets of mpoints are in disjoint vertical strips, and Steiner points can be added arbitrarily close to the points of S, there are no intersections between the 2-factors constructed in different steps of the procedure. Thus, procedure Steiner-cycles uses at most m 2Steiner points for each group of mpoints of S.Sincemis odd, then for every group of mpoints we use m−1 2Steiner points and so the total number is m−1 2 n m. Observe that the conditions m⩾5 and modd are necessary since for groups of m<5points,thenumberof Steiner points needed to construct the cycles is much higher, and meven gives rise to n 2Steiner points. It is easy to check that m=5 is the value that gives the best performance, obtaining 2n 5Steiner points. When the cardinality of Sis not divisible by five, we have to add at most four Steiner points to the quantity above to construct a 2-factor with the last points of the set. Thus, from the discussion above we have the following theorem. Theorem 3.2. 2 5n+4Steiner points suffice to construct a 2-factorofS,whichcanbefoundinO(nlogn)time. The ideas of Theorems 3.1 and 3.2 are now extended to 3-, 4-, and 5-factors. Theorem 3.3. Let S=R∪B. Then n +4,2nand5nSteiner points suffice to construct two monochromatic non-crossing 3-, 4-and5-regular graphs, respectively. Moreover, there exists an algorithm which finds such graphs in O (nlogn)time. Proof. Suppose first that Rand Bare not line-separable and apply procedure Steiner-cycles obtaining two nested monochromatic cycles CRand CB. Recall that the cycles are constructed by sorting the points of Rand Bangularly from a point p∈CH(R)∩CH(B), adding Steiner points when necessary. Assume that CRis the inner cycle (the process is analogous for the outer cycle CB). To obtain a 3-factor, split the points of CRinto consecutive triplets with respect to the order given by p.Add a Steiner point close to the midpoint of each triplet on the line that joins it with p, and also join all the points of every triplet to the corresponding Steiner point (see Fig. 3(a)). If |CR|is not divisible by 3, then there are one Fig. 3. (a) Three triplets with their respective Steiner points, and two points left. (b) Adding two Steiner points and new adjacencies in the graph of (a) to obtain a 3-factor. Fig. 4. (a) A 4-factor, (b) A 5-factor. or two points left (Fig. 3(a)) for which extra Steiner points can be added as follows. Suppose that we have two points left (similar for one) and consider the previous and next points, in the angular order, to our consecutive points. Add a Steiner point for each of them on the line that joins them with pand also add the adjacencies shown in Fig. 3(b) to obtain degree three. Note that since the points are angularly sorted around a point inside our resulting graph, there are no crossings. Observe also that for the outer cycle, the points are added close to the midpoint of each triplet outside the cycle. Thus, we use at most |CR|+|CB| 3+4⩽1 3(n+n 2)+4 Steiner points plus the at most n 2Steiner points used to construct the monochromatic cycles CRand CB.Hence,the total number is at most n+4. A 4-factor is obtained by placing a copy of the inner cycle CR(analogous for the outer cycle CB), say C1 R,inside (resp. outside) it and joining every point of CRto two consecutive points of C1 Ras it is illustrated in Fig. 4(a). Due to the angular construction of the cycles, every edge can be drawn without intersection, obtaining a 4-factor. This process adds one new Steiner point for every point of CRand CBsince the copies C1 Rand C1 Bare formed only by Steiner points, i.e., at most n+ n 2,plusatmostn 2to construct the cycles. Thus, the total number of Steiner points is at most 2n. Finally, a 5-factor can be obtained from the previous 4-factor as follows (see Fig. 4(b)). Add one Steiner point siin each edge eiof C1 R, draw a copy of CRinside C1 R, and call it C2 R.Joinsito three vertices: the common neighbor of the endpoints of eiin CRand the endpoints of the copy of eiin C2 R.Alsojointhetwoendpointsofeito the endpoints of the copy of eiin C2 R. Proceed analogously for D. Garijo et al. / Information Processing Letters 114 (2014) 19–24 23 Table 1 Summary of the obtained bounds. Steiner points White points Both 1-factors n/7[4,9] n(tight) n−mwhite and m/3Steiner 2-factors 2n/5+O(1)2n(tight) 2n−mwhite and mSteiner 3-factors n+4N/A N/A 4-factors 9n/5+10 N/A N/A 5-factors 23n/5+24 N/A N/A the cycle CB. Since the copies of CRand CBare formed by Steiner points, the total number of Steiner points used is 5n. Suppose now that Rand Bare line-separable. Then, we proceed as above independently for CRand CBconsidering the angular order given by points inside CH(R)and CH(B), respectively, as procedure Steiner-cycles describes. 2 Asinthecaseof2-factors,wecanreducethenumber of Steiner points used to obtain 4- and 5-factors by decreasing the connectivity of the resulting graph. The process is analogous to the one described for 2-factors, obtaining again the best performance for m=5. The case k=3 cannot be improved using this method since the bound on the number of Steiner points is the same when taking the points in groups of mand when considering just the whole set S. Thus, the following bounds are obtained for 4- and 5-factors, where the constants come from the remaining points of Swhen Sis not divisible by five. Theorem 3.4. Let S =R∪B.Then 9 5n+10 Steiner points suffice to construct a 4-factor of S, and 23 5n+24 Steiner points suffice to construct a 5-factor of S. Moreover, there exists an algorithm which finds such factors in O(nlogn)time. Another approach to the problem of constructing k-fac- tors is to use white points (considered also in Section 2). We establish a tight bound for k=2, and show that this result cannot be extended to k>2(Proposition 3.6)since there are point configurations for which it is not possible to obtain a k-factor independently of the color of the points. It can be easily shown that 2nwhite points can be necessary to construct a 2-factor when no Steiner points are used. It suffices to consider the points on a circle, locating all the white points on one hemisphere and the colored points alternating in color in the other hemisphere. Any segment matching, say two red points, will eventually leave a blue point isolated. Hence, a 2-factor must be constructed by matching each colored point with two white ones. Note that the final 2-factor is a collection of triangles. On the other hand, Theorem 2.3 guarantees that a k-factor can always be constructed by using 2nwhite points. Considering a=1, b=2, and g=n,weobtain nconvex sets containing just one colored point and two white points. The union of these triangles is a 2-factor. Thus, we have the following theorem. Theorem 3.5. 2nwhite points are always sufficient and sometimes necessary to obtain a 2-factor of S =R∪B. Such a2-factor can be constructed in O(n4/3log4n)time. When the number of white points is smaller that 2n, say 2n−m, it might be necessary to replacing the missing white points with mSteiner points. Observe that if m> 2 5n,Theorem 3.2 implies that it is better to construct the 2-factor using only Steiner points. Proposition 3.6. For k >2it is not possible to construct a k-factor of a point set in convex position. Proof. LetΩbe a set of points in convex position. Suppose on the contrary that there exists a k-factor Fof the set Ω for k>2, and consider its dual graph F∗.Letube the vertex in F∗corresponding to the unbounded face of F, and Gthe graph obtained by deleting vertex uin F∗. Since the points of Ωare in convex position, then every diagonal splits the point set into two parts. This implies that Ghas no cycles and so is a forest. A leaf in Gcorresponds to a face fin Fthat has a unique adjacent bounded face. Hence, all vertices in fbut two have degree 2; a contradiction since Fis k-regular and k>2. 2 Remark 3.7. As mentioned, Theorem 3.5 cannot be extended to k-factors when k>2. Indeed, the above result says that given a set Sof red and blue points and any number of white points, all of them in convex position, it is not possible to construct a k-factor and so we have configurations of points for which no k-factor can be obtained independently of the number of white points used. One might try to use similar arguments as those used in Theorem 3.5 to construct 3-, 4-, and 5-factors using white points and also Steiner points: split the plane into convex regions containing one colored point and two white points and add 1, 3, or 9 Steiner points inside the triangle to obtain a 3-, 4-, or 5-factor, respectively. Nevertheless, the number of Steiner points that this procedure requires is greater than the number of Steiner points needed to construct the k-factor without considering white points (see Theorem 3.3). 4. Conclusion Table 1 summarizes some of the bounds obtained in this paper. As a consequence of Proposition 3.6 the study for 3-, 4- and 5-factors cannot be extended to white points or combinations of both types of auxiliary points. It would be interesting to find better strategies for combining Steiner and 24 white points, and also to study if the bounds on Steiner points are tight. Acknowledgements We thank to two anonymous referees for their many useful suggestions and comments, which helped improve the paper substantially. References [1] G. Aloupis, J. Cardinal, S. Collette, E.D. Demain, M. Demain, M. Dulieu, R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara, P. Taslakian, Non-crossing matching of points with geometric objects, Comput. Geom. 46 (1) (2013) 78–92. [2] S. Bespamyatnikh, D. Kirkpatrick, J. Snoeyink, Generalizing hamsandwich cuts to equitable subdivisions, Discrete Comput. Geom. 24 (2000) 605–622. [3] G. Brodal, G. Jacob, Dynamic planar convex hull, in: Proceedings 43rd Annual Symposium on Foundations of Computer Science, 2002, pp. 617–621. [4] A. Dumitrescu, R. Kaye, Matching colored points in the plane: Some new results, Comput. Geom. 19 (2001) 69–85. [5] M.R. Garey, R.L. Graham, D.S. Johnson, The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32 (4) (1977) 835–859. [6] D.Garijo,M.A.Garrido,C.I.Grima,A.Márquez,A.Moreno-Gonzalez, J.R. Portillo, R. Robles, J. Valenzuela, Monochromatic geometric k-factors in red–blue sets with white and Steiner points, in: J. Nešetˇ ril, A. Raspaud (Eds.), EuroComb 2009: European Conference on Combinatorics, Graph Theory and Applications, Bordeaux, France, in: Electronic Notes in Discrete Mathematics, vol. 34, 2009, pp. 151–155. [7] F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Ann. Discrete Math., vol. 53, Elsevier, North-Holland, 1992. [8] H. Ito, H. Uehara, M. Yokoyama, Two-dimensional ham-sandwich theorem for partitioning into three convex pieces, in: M. Kano, J. Akiyama (Eds.), JCDCG 1998: Japan Conference on Discrete and Computational Geometry, Tokyo, Japan, in: Lecture Notes in Computer Science, vol. 1763, Springer-Verlag, 2000, pp. 129–157. [9] A. Kaneko, M. Kano, Discrete geometry on red and blue points in the plane – a survey–, Discrete Comput. Geom. 25 (2003) 551–570. [10] N. Megido, Linear-time algorithms for linear programming in R3and related problems, SIAM J. Comput. 12 (4) (1983) 759–776. [11] T. Sakai, Balanced convex partitions of measures in R2,GraphsComb. 18 (1) (2002) 169–192. [12] M. Sarrafzadeh, C.K. Wong, Bottleneck Steiner trees in the plane, IEEE Trans. Comput. 14 (3) (1992) 370–374.