Quadrangulations and 2-Colorations

EWCG 2005, Eindhoven, March 9–11, 2005 Quadrangulations and 2-Colorations Carmen Cort´es∗¶ Alberto M´arquez†¶ Atsuhiro Nakamoto‡Jes´us Valenzuela§¶ Abstract Any metric quadrangulation (made by segments of straight line) of a point set in the plane determines a 2-coloration of the set, such that edges of the quadrangulation can only join points with different colors. In this work we focus in 2-colorations and study whether they admit a quadrangulation or not, and whether, given two quadrangulations of the same 2-coloration, it is possible to carry one into the other using some local operations, called diagonal slides and diagonal rotation. Although the answer is negative in general, we can show a very wide family of 2-colorations, called onions 2-coloration, that are quadrangulable and which graph of quadrangulations is always connected. 1 Introduction Given a set S, either a polygon or a point set, a quadrangulation of Sis a partition of the interior of S,if Sis a polygon, or of the convex hull of S,ifSis a point set, into quadrangles (quadrilaterals) obtained by inserting edges between pairs of points (diagonals between vertices of the polygon) such that the edges intersect each other only at their end points. Not all polygons or point sets admit quadrangulations, even when the quadrangles are not required to be convex. In the study of finite element methods and scattered data interpolation, it has recently been shown that quadrangulations of point sets may be more desirable objects than triangulations [2]. The quadrangulations of polygons have been also investigated in Computational Geometry, mostly in the context of guarding or illumination problems. From now on we call a polygon or point set quadrangulable if it admits a quadrangulation without adding any additional point (Steiner point). There are two different characterizations of quadrangulable point sets: ∗Department of Applied Mathematics I, University of Seville, ccortes@us †Department of Applied Mathematics I, University of Seville, [email protected] ‡Department of Mathematics, Yokohama National University, [email protected] §Department of Mathematics, University of Extremadura [email protected] ¶Partially supported by MCyT project BFM2001-2474. •if and only if there exists a triangulation of the set such that its dual graph contains a perfect matching [5]. •if and only if it has an even number of points in its convex hull [1]. A quadrangulation is constructed (with the addition of a Steiner point to obtain an even number of points in the convex hull, if necessary) in Θ(nlog n). For a more complete vision on quadrangulations we recommend Toussaint’s survey [6]. Given a quadrangulation of a point set in the plane, it determines a 2-coloration of the set, such that edges of the quadrangulation can only join points with different colors. In this work we focus on 2-colorations and study whether they admits a quadrangulation or not (Section 2), and whether, given two quadrangulations of the same 2-coloration, it is possible to carry one into the other using some local operations (Section 3). Finally, in Section 4 we present a very wide family of 2-colorations, called onions 2coloration, that are quadrangulable and which graph of quadrangulations is always connected. 2 2-colorations and quadrangulations Suppose we have a 2-colorated point set Sin the plane andwewanttoknowifitispossibletoconstructa quadrangulation of its convex hull. A similar condition to the one given by [1] is, in this context, evident: Lemma 1 A necessary condition for a 2-coloration of a point set Sto admit a quadrangulation (to be quadrangulable) is that 1. the number of points of the convex hull of Sis even; and 2. consecutive points of the hull have different color. But even when the conditions of Lemma 1 are fulfilled, it is easy to find non-quadrangulable 2colorations, as the one at the left of Figure 1. In order to construct a quadrangulation, point 1 cannot be joined with cbecause then bcan be joined with no black point but 1. So we draw an edge from 1 to b.Nowbcannot be joined either with 3 or with 4, because then cor 2, respectively, would be isolated, and cannot be part of any quadrangulation. But if 65 21st European Workshop on Computational Geometry, 2005 we join bwith 2 the only way to complete a quadrilateral is to match 2 and d, that leaves 3 isolated. It is important to remark that we are talking about 2-colorations instead sets of points. Thus, while the 2-coloration at the left of Figure 1 is not quadrangulable, the underlying point set is, as we see in the right picture. a b c d 1 2 3 4a b c d 1 2 3 4 Figure 1: The set is either quadrangulable or not depending on the coloration. Notice that in the right picture we have interchanged the colors of 2 and b, obtaining a set with two convex layers, both of them made by points with alternate colors. This is a interesting configuration since, as we will see in Section 4, it is always quadrangulable. 3 Diagonal transformation in quadrangulations Nakamoto [4], working with topological quadrangulations on surfaces, defines two diagonal transformations; the diagonal slide and the diagonal rotation, that are shown in Figure 2. Note that, while the diagonal slide does not modify the coloration of the set, the diagonal rotation changes the color of the center of rotation (because, in other case, points with the same color are joined). Since the same point set can have different colorations, it is not always possible to change any two quadrangulations one into each other using only diagonal slides. In Figure 3 two colorations of the same point set are shown; one with four black and four white points, and another with five white and three black points. Since diagonal slides preserve colorations, it is not possible to use them to transform one quadrangulation into the other. However, it is easy to see that this can be done using also diagonal rotations. Nakamoto [4] proved that in any closed surface it is always possible to carry one topological quadrangulation of a set into any other if 1. both diagonal slides and rotations are allowed; or 2. both quadrangulations have the same number of points of each color by using only diagonal slides. diagonal slide diagonal rotation Figure 2: Diagonal transformations on quadrangulations. Figure 3: Quadrangulations of the same set with different colorations. This can be seen in terms of the connectivity of the graph of quadrangulations. The graph of quadrangulations of a point set is the graph having all the quadrangulations of the set as nodes, and with adjacentcies corresponding to diagonal slides or diagonal rotations. Similarly, the graph of quadrangulations of a 2-coloration has as nodes the quadrangulations of a given 2-coloration. Since diagonal rotations change the 2-coloration, the adjacentcies are determined only by diagonal slides. Both graph of quadrangulations are, in general, not connected. In Figure 4, it is shown a 2-coloration that admits only two quadrangulations, being not possible to perform any diagonal slide. If we also allow diagonal rotations it can be shown that it is not possible to transform one quadrangulation into the other. This gives rise to the following theorems: Theorem 2 There are 2-colorations with disconnected graph of quadrangulations. Theorem 3 There are point sets with disconnected graph of quadrangulations. 66 EWCG 2005, Eindhoven, March 9–11, 2005 Figure 4: A set with disconnected graph of quadrangulations. Our example has disconnected graph of quadrangulations both as a 2-coloration and as a point set. An open problem is to determine if both things always come together, or if there exit point sets with connected graph of quadrangulations that admit 2colorations which graph of quadrangulations is not. In spite of the graph of quadrangulations of an arbitrary 2-coloration is, in general, not connected, in the next section we present a wide family of 2-colorations having this property. 4 Onion 2-colorations If a set of sites have an even number of vertices in its convex hull, then it is quadrangulable, and vice-versa [1]. This is rewritten for 2-colorations in Lemma 1, but only as a necessary condition, since we find nonquadrangulable 2-colorations that fulfill it, as the one we saw in Figure 1. But, what about if we extend Lemma 1 to the interior of the set? If the convex hull of the 2-coloration fulfill the lemma, we remove it and examine the convex hull of the remaining points, and so on. A 2-coloration with this property is quadrangulable and its graph of quadrangulations is connected. We call onion 2-coloration to a 2-coloration of a point set such that all its convex layers have an even number of points with alternate colors. An onion layer of an onion 2-coloration is the set of edges that are part of a convex layers of the set. We call Oi, with i=0,...,l, to the onion layers of the onion 2-coloration, such that Oiis inside the polygon defined by Ojif i>j(Figure 5). Note that the polygon defined by Oldoes not contain any point of the onion 2-coloration and that O0, the convex hull, is always included in every quadrangulation of the onion 2-coloration. By definition, the points on every onion layer satisfy Lemma 1, that implies the following result. Proposition 4 Onion 2-colorations are quadrangulable. The main idea of the proof is to draw a triangulation joining points between two consecutive onion layers. By deleting the edges matching points with the O0 O1 Ol Figure 5: An onion 2-coloration and its onion layers. same color (Figure 6) we obtain a quadrangulation of the onion 2-coloration. It should be note that we are drawing quadrangulations of convex polygons with a convex hole, being the general case, decide whether a polygon with holes admits a quadrangulation, an NP-complete problem [3]. Figure 6: By deleting the diagonals between points with the same color we obtain quadrilaterals. But onion 2-colorations are not the only quadrangulable 2-colorations, since there are quadrangulable 2-colorations with non alternate colors in some of its convex layer (Figure 7) or with a odd number of points on them. Figure 7: The colors of the inner convex layer are not alternate. In addition to be quadrangulable, onion 2colorations have connected graph of quadrangulations. The proof is based in the following lemmas: 67 21st European Workshop on Computational Geometry, 2005 Lemma 5 Given two quadrangulations of an onion 2-coloration containing all their onion layers, we can transform one into the other by only using diagonal slides. Lemma 6 Any quadrangulation of an onion 2coloration can be carried into another containing its onion layers using diagonal slides. From these lemmas it can be easily proved the connectivity of the graph of quadrangulations of any onion 2-coloration. Theorem 7 The graph of quadrangulations of an onion 2-coloration is non-empty and connected. In particular, if the onion 2-coloration have only one layer, we obtain the following result: Corollary 8 The graph of quadrangulations of any quadrangulable 2-coloration in convex position is connected. 5 Conclusions and open problems Two main ideas can be extracted from this work: to be quadrangulable depends on the 2-coloration of the set, and the graph of quadrangulations of both a 2coloration and a point set is, in general, not connected. However, there exits a wide family of 2colorations, the onion 2-colorations, that are quadrangulable and which graph of quadrangulations is connected. There are several questions that appear all along the present work. One is to explore new conditions for a 2-coloration to be quadrangulable, searching for new families of quadrangulable 2-colorations. Related to the graph of quadrangulations, an interesting approach is to study the relationship, if it exits, between the connectivity of the graph and the coloration of the set. And, since the example presented (Figure 4) of a set with disconnected graph of quadrangulations have rows with until four collinear points, it would be convenient to construct a new example in general position. Probably this implies to work with sets with greater cardinal and complexity. Finally, another line for future works is, since they also admit 2-colorations, to extend this study from quadrangulations to 2n-lations of point sets. References [1] P. Bose and G. Toussaint. Characterizing and efficiently computing quadrangulations of planar point sets. Computer Aided Geometric Design, vol. 14, 1997, pp. 763-785. [2] M. L. Lai and L. L. Schumaker. Scattered data interpolation using piecewise polynomials of degree six. SIAM Numer. Anal., 34(1997), pp.905– 921. [3] A. Lubiw Decomposing polygonal regions into convex quadrilaterals. Proc. Symposium on Computational Geometry, 1985, pp. 97–106 [4] A. Nakamoto. Diagonal transformations in quadrangulations of surfaces. J. Graph Theory, 21:289–299, 1996. [5] S. Ramaswami, P. Ramos and G. Toussaint. Converting triangulations to quadrangulations Computational Geometry: Theory and Applications, Vol. 9, March 1998, pp. 257-276. [6] G. Toussaint. Quadrangulations of planar sets. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, pages 218– 227. Springer-Verlag, 1995. 68