Compatible spanning trees

Compatible Trees∗ Alfredo Garc´ıa 1Clemens Huemer 2Ferran Hurtado 3Javier Tejel 1 Abstract Two plane geometric graphs are said to be compatible when their union is a plane geometric graph. Let Sbe a set of npoints in the Euclidean plane in general position and let Tbe any given plane geometric tree whose vertex set is S. The main problem we consider in this work consists of finding a second plane geometric tree T0on S, such that T0is compatible with Tand shares with Ta minimum number of edges. We prove, up to additive constants, that there is always a compatible plane geometric tree T0having in common with Tat most n/4 edges; while for some plane geometric trees T, any other tree T0spanning S, compatible with T, has at least n/5 edges in common with T. 1 Introduction Preliminaries. Throughout this paper let Sbe a given set of n≥3 points in the Euclidean plane in general position, in the sense that no three of them are collinear. We denote by K(S) the complete geometric graph on top of S, i.e., the graph with vertex set Swhose edges are all the straight-line segments connecting two points in S. A geometric graph on Sis a subgraph Gof K(S). A geometric graph Gis plane if no two edges of G intersect except possibly at a common vertex. Plane geometric graphs are also known in the literature as plane straight line graphs or as crossing-free or non-crossing subgraphs of K(S). Unless specified otherwise, all geometric graphs considered in this paper are plane and have as vertices the same set of points S. Two plane geometric graphs are said to be compatible if their union is also a plane geometric graph. A geometric graph that is compatible with a given geometric graph G will be called G-compatible. Purpose of this article. In this paper we focus on the following problem: Given a plane geometric tree Ton S, find another plane geometric tree T0spanning S, such that Tand T0are compatible and T0has a minimum number of edges in common with T. We will denote by d(T) this minimum number of common edges between Tand any other T-compatible tree T0. ∗Work partially supported by projects MICINN MTM2009-07242, MINECO MTM2012-30951 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: MICINN Project EUI-EURC-2011-4306. In addition, the first and fourth authors are also supported by project E58-DGA, and the second and third authors by project Gen. Cat. DGR2009SGR1040. 1Departamento de M´etodos Estad´ısticos, IUMA, Universidad de Zaragoza, Zaragoza, Spain. olaverri@ unizar.es,[email protected]. 2Departament de Matem`atica Aplicada IV, Universitat Polit`ecnica de Catalunya, Barcelona, Spain. [email protected]. 3Departament de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya, Barcelona, Spain. [email protected]. 1 In general, d(T) depends on the abstract tree Tand also on the position of the points of S, and can be seen as a measure of the obstruction caused by T. For example, d(T) = 0 would mean that Tis no obstruction at all, as a disjoint plane spanning tree compatible with Tcould still be drawn on top of S; on the contrary, a high value of d(T) would mean that no much room is left for the edges of a second tree. This degree of obstruction is also a measure of the visibility between the points of Swhen the edges of Tare considered as obstacles, and hence our work overlaps the area of Art Gallery Problems, as mentioned below in more detail. The computation of the exact value of d(T), for a given input tree T, appears to be a difficult problem. However, for some special cases d(T) is easily obtained. For example, if Tis a star, then d(T) = 1, because we can connect the leaves by a path in radial order around the unique internal node, which has to be reached by one of edge already in T. When the npoints of the set Sare in convex position, it is easy to see that d(T) = 1 for any tree T. Situations in which d(T) can be arbitrarily large are shown in Figures 20 and Figure 21. Therefore, it is natural to study the extremal value dn= max {S,T }d(T), where Sis any set of npoints in the plane, and Tany plane geometric tree spanning S. In this paper we give combinatorial bounds on dn, which we describe precisely in the summary of results below, and we also show that the parameter d(T) can be derived from the analysis of the triangulations of Sthat are compatible with T. Previous related research. Problems on compatibility of plane graphs, combining visibility issues and augmentation questions, have been receiving substantial attention in computational geometry since the mid eighties to the present. To augment a graph G consists of adding edges to G, ideally in minimum number, to obtain some properties or structure in the resulting augmented graph G0. In our context, we focus on the case in which Gand G0are plane and compatible; for this topic we refer the interested reader to the thorough survey [17]. One of the oldest problems in this field is, given a set Mof segments (i.e., a crossingfree geometric matching of the set Sof their endpoints), to find conditions and decision algorithms for the existence of a plane Hamiltonian cycle spanning Sand containing M[24, 25]. As this is not always possible, several alternative conjectures and partial results arose [21, 28, 23], culminating with the proof by Hoffmann and T´oth [14] that a compatible Hamiltonian cycle always exists, i.e., a polygonization Pof Sin which all the segments in Mare either sides of the polygon P, or internal diagonals of P, or external diagonals of P. A quite similar problem was posed and discussed in [3]: Given a non-crossing perfect matching on a point set S, one wants to find another non-crossing perfect matching that is compatible and edge-disjoint with the given one. A solution in the affirmative has been obtained very recently by Ishaque et al. [19] when there is an even number of segments (disjointness is not always possible when the number is odd, as proved in [3]). The preceding problems have often been studied as visibility problems, considering the input data as “obstacles” for the visibility between segment endpoints. For this viewpoint and related visibility questions, we refer the reader to the surveys [6, 22, 29]. With more emphasis on the augmentation aspects for geometric graphs, we can mention the family of results on augmenting a plane perfect matching to become a compatible plane tree with “good properties” [7, 8, 16], or the large set of works on compatibly 2 augmenting given plane graphs to improve on their vertex-connectivity or their edgeconnectivity [1, 12, 5, 26, 27]. Problems in which the vertices of the initial graph are colored and the augmentation has associated constraints have also been studied, as for trees in [13, 16] and for compatible matchings (for example in the thesis [30]). Other related problems, leaning towards the topic of simultaneously drawing two graphs, are discussed in [9, 10, 11, 18, 20]. Finally, it is worth mentioning that another family of compatibility problems is related to the idea of morphing graphs. For example, given two crossing-free geometric trees Taand Tb, spanning the same set of npoints, there is always a sequence of trees T0=Ta, T1, . . . , Tk−1, Tk=Tb, with k∈O(log n), in which every two consecutive trees are compatible [2]. Similar results have been obtained for other configurations, such as matchings [3, 15], and (in the negative) for pointed pseudotriangulations [4]. A major open problem in the area is whether this kind of sequences exist or not for polygonizations, or for spanning paths, of any given point set. Spanning trees and compatible triangulations. There is another way, non obvious yet fundamental, to look at the parameter d(T) of a plane geometric tree T. Let us add edges to T, while keeping plane the augmented geometric graph, until this addition of edges is not possible any more. In this way, we obtain a T-compatible triangulation ∆ of S. Let c∆(T) be the number of connected components of the subgraph ∆ −T, formed by the edges added to T. Let c(T) = min∆c∆(T) be the minimum of the values c∆(T) taken over all possible T-compatible triangulations ∆. We state in Lemma 1 at the end of this section that d(T) = c(T)−1. This is, c(T) = d(T) + 1 gives the minimum number of components that we can obtain in any spanning subgraph of K(S) that uses edges (segments) that neither cross nor coincide with those of T. We will call the edges of the given tree Tblack edges, and the edges added to Tfor obtaining a compatible triangulation ∆red edges. The connected components of ∆ −Twill be called the red components of ∆. Therefore, our problem translates now to finding a T-compatible triangulation having a minimum number of red components. See Figure 1. Figure 1: Left: A tree Tand a compatible triangulation ∆. Right: The three components of the “red” graph ∆ −T(one of them is an isolated vertex). We use thick lines for black edges, and thin lines for red edges; in this way the difference is still visible when a black and white printer is used. Results Our study of d(T) is built up on the relationship between this value and the minimum number c(T) of connected components in any spanning subgraph of K(S) that uses edges 3 (segments) that neither cross nor coincide with those in T, made precise in the following statement, proved in Section 2.2: Lemma 1. d(T) = c(T)−1. The study of c(T) requires the introduction of several definitions, intermediate results, and the proof of many technical lemmas, some of them with a non-short proof. Therefore, for the ease of understanding, we have made the option of stating in this section the most relevant results, and presenting the corresponding proofs in Section 2. If uand vare two consecutive vertices of the convex hull of S,CH(S), and uv /∈T, there is a unique path in pin Tthat connects uand v. The polygonal region bounded by uv and pis what we call a pocket of the tree T(roughly speaking, the precise definition is given in Section 2). The nature of the pockets, and the way they interact, is the back spine of the series of results that lead to Propositions 1 and 2, stated and proved in Section 2.6, which tell us that there are essentially two types of trees: On one hand, there are the trees that admit a compatible triangulation ∆ having one big red component containing at least 3n 4of the vertices, while all the other components, if any, are interior isolated vertices; on the other hand, there are the trees in which ∆ −Thas exactly two components, each one containing at least one vertex from CH(S). The triangulations of the latter type have d(T) = c(T)−1 = 1, while this parameter clearly depends on the number of isolated vertices for the first type of triangulations. On the light of the preceding considerations, one can see why the following theorem, proved in Section 2.7, plays a crucial role in our analysis of d(T): Theorem 1. Let Tbe a geometric tree. Then there is a T-compatible triangulation ∆0such that ∆0−Tcontains at most n−3 4isolated vertices in addition to a unique large component. On the other hand, there are geometric trees T, such that any T-compatible triangulation ∆gives at least n−2 5isolated vertices in ∆−T. Combining Theorem 1, the preceding discussion, and Lemma 1, we immediately obtain our main result, which provides combinatorial bounds for dn: Theorem 2. For every integer n≥3the following inequalities hold: n−2 5≤dn≤n−3 4. In other words, for every set Sof npoints and every plane geometric tree Tspanning K(S), there is a compatible tree T0sharing at most n−3 4edges with T, and there are some sets Swith |S|=nand plane geometric spanning trees Tsuch that any T-compatible tree has at least n−2 5edges in common with T. In the section in which we prove Theorem 1 we provide as well some evidence that the tight value of dnappears to be close to the lower bound in Theorem 2, which leads us to formulate the following conjecture: Conjecture 1. For some constant c, we have dn=n 5+c, for every integer n≥3. As for results, in the last section of the paper we prove two additional theorems that are easily derived from the generic framework we construct, but that we consider interesting on their own: Theorem 3. Let Tbe a simple spanning path. Then, we can find a T-compatible triangulation ∆such that the number of components of ∆−Tis at most 2, and hence d(T)≤1. 4 Theorem 4. Let Γbe a simple polygon with vertex set S. Then, we can always find aΓ-compatible triangulation ∆(which in general will have edges inside and outside Γ), such that the number of connected components of ∆−Γis at most 3. Moreover, if Γis non-convex, this minimum achievable number of components is 1or 2. 2 Proofs 2.1 Basic definitions. Organization of the section Let us remind first some common definitions and notations for simple polygons. Let q1, . . . , qnbe the vertices of a simple polygon Pgiven in clockwise order; the arithmetic of their indices is done modulo n. We say that the vertex qiis convex if the angle between the vectors −−−→ qiqi−1and −−−→ qiqi+1 is less than π, and that it is reflex otherwise. A diagonal qiqj, when we consider it as oriented from qito qj, divides the polygon Pinto two polygons: the left polygon PL, whose vertices are the vertices of Pfrom qito qjin clockwise order, and the right polygon PR, whose vertices are the vertices from qjto qiin clockwise order. If we place the maximum possible number (n−3) of non-crossing diagonals inside P, we obtain a triangulation ∆ of P. We will always assign red color to the diagonals of the triangulations we are using. We call weakly simple polygon a plane geometric graph consisting of the union of a cycle with trees rooted at the vertices of the cycle, having all their additional vertices in the internal face of the cycle. See Figure 2, left. If we traverse clockwise the boundary of the unique bounded face of the weakly simple polygon, some vertices are visited several times before reaching the starting point of the traversal, as shown in Figure 2, center. However, the list of visited vertices, with the repetitions, behaves a as a simple polygon regarding many geometric properties (in particular regarding its triangulation with internal diagonals), which is obvious if one thinks of a weakly simple polygon as a proper simple polygon by splitting the multiple vertices into points that are infinitesimally close as shown in Figure 2, right. Figure 2: Left: A weakly simple polygon P. Center: traversal of the inner boundary of P. Right: simple polygon equivalent to P. We will denote by {v1, . . . , vn}the set of vertices of a point set S, which will also be the vertices of any crossing-free geometric tree Tspanning S. The convex hull of Swill be denoted by CH(S). If a vertex of Sis also a vertex of CH(S), we will also denote this point by qi, in such a way that the vertices of CH(S) are q1, . . . , qk, in clockwise order. If ei=qiqi+1 is not an edge of T, adding eito Tyields a unique bounded face; the red edge eiand the black interior boundary of the face form a weakly simple polygon. We call these weakly simple polygons the pockets of T. Observe that any T-compatible triangulation ∆ is obtained by triangulating all the pockets of T. The pockets of Tcan be seen as a decomposition of the convex polygon CH(S) into 5 (weakly) simple polygons. In order to simplify some forthcoming proofs, we have to consider some very similar yet slightly more general situation: Let Qbe any simple polygon with vertices q1, . . . , qkin clockwise order, and let Tbe any non-crossing geometric tree spanning all the vertices in Qand having possibly some other vertices that are points inside Q, satisfying the condition that all the edges of Tare either inside Qor are sides of Q. As before, each edge eiof Qthat is not an edge of T defines a pocket of T. If P1, . . . , Phare the pockets of T, we also require that Property (W): If a vertex qi∈Qbelongs to a pocket Pj, then qiis a convex vertex of the weakly simple polygon Pj. In this situation a T-compatible triangulation ∆ will be a triangulation of all the pockets of T, that is to say, only edges inside Qor on the boundary of Qwill be considered to obtain ∆. See Figure 3. The number of red components of ∆ will be c∆(T) and c(T) will be the minimum among all c∆(T). Usually, in the figures we will represent the edges of Q as red curved segments, specially if they coincide with edges of T(always drawn in black). Throughout the paper, when we say that a polygon (in general denoted as Q, Q0, Q1, . . .) encloses a tree, we assume that all the vertices placed on that polygon satisfy condition (W). T qiqi+1 Q Pi Figure 3: A tree Tenclosed in a polygon Q. The vertices of Qhave to be convex in each incident pocket. The remainder of this section is organized as follows. We start with the proof of Lemma 1. Then, in Subsection 2.3, we study the case in which all pockets are convex polygons. The case of all the pockets being simple polygons, or equivalently, that all the leaves of the geometric tree Tare on the boundary of Q, and the general case of pockets being weakly simple polygons, are studied in Subsection 2.4. Subsection 2.5 focuses on general properties of all T-compatible triangulations. The main results relating trees and compatible triangulations are given in Subsection 2.6. Finally, we consider in Subsection 2.7 the bounds on the number of red components of a T-compatible triangulation ∆, given a plane geometric tree T, this is, Theorem 1, from which Theorem 2 has been derived in the Introduction, and we conclude in Subsection 2.8 with some observations on special cases, namely the proofs of Theorem 3 and Theorem 4. 6 Q T qi qj Figure 4: A tree with convex pockets and vertices on Q. 2.2 Proof of Lemma 1 Proof. We have to show that d(T) = c(T)−1. Let T0be a spanning tree having d(T) common edges with T. The n−1−d(T) red edges of T0form a spanning forest consisting of d(T)+1 red trees, some of which might be singletons, and form together a spanning red subgraph of T0, with d(T) + 1 red components. If we add more red edges until completing T∪T0to a compatible triangulation, the number of red components cannot increase, hence c(T)≤d(T) + 1. Now, suppose that ∆ is a T-compatible triangulation that has c(T) red components C1, . . . , Cc(T). Since ∆ is connected, and there are no red edges connecting any two red components Ciand Cj, there must exist c(T)−1 black edges between different red components yielding a connected spanning graph M, with c(T)−1 black edges. Therefore, any spanning tree T0of Mwill be compatible with Tand will have at most c(T)−1 black edges, therefore d(T)≤c(T)−1. 2.3 Trees with convex pockets Let Tbe a tree inside or on the boundary of a simple polygon Q, with all the pockets being convex polygons. We prove in the following lemmas that in this case c(T) is either 1 or 2, and that we can determine the correct value for any such tree. Lemma 2. Let Qbe a simple polygon with vertices q1, . . . , qk, with k≥3, and let Tbe a geometric tree having the same set of vertices as Q, whose edges are either sides or internal diagonals of Q, and such that all the pockets of Tare convex. See Figure 4. Then: i) There is no T-compatible triangulation of Qhaving only one red component. ii) Given any edge e=qiqjof T, there is a T-compatible triangulation ∆of Qthat has exactly two red components, one containing vertex qi, and the other one containing vertex qj. 7 Q T qi qj Figure 5: Left: Base of the induction. Right: Case in which Tis a convex path. Proof. i) The polygon Qhas kvertices and any triangulation of Qconsists exactly of 2k−3 edges, namely k−3 internal diagonals and the ksides of Q. Hence, a T-compatible triangulation ∆ contains k−1 black edges and k−2 red edges. Therefore, any spanning tree T0of ∆ contains at least one black edge, which implies that d(T)≥1 and consequently c(T)≥2. Let us prove ii) by induction on k. For k= 3 the result is obvious. See Figure 5. Let us assume that k≥4, and that the result is true for polygons Q0having less than kvertices. First, suppose that some diagonal d=q0 iq0 jis an edge of T(dmight coincide with e). Then ddivides Qinto two polygons Q1and Q2, each one containing a spanning subtree, in which we can apply induction. Suppose that eis in polygon Q1. By induction, we can triangulate Q1in a way that one component A1contains qiand the other component B1 contains qj. In the same way we can triangulate Q2having one component A2containing q0 iand the other component B2containing q0 j. These triangulations of Q1and Q2form together a compatible triangulation ∆ of Q. In addition, if q0 iand q0 jare in the same component of Q1, say A1, then ∆ has precisely two components, A1∪A2∪B2containing qi, and B1containing qj. In the same way, if q0 iand q0 jare in different components of Q1, say A1and B1, respectively, then ∆ has again two components, A1∪A2containing qi, and B1∪B2containing qj. Finally, if all the edges of Tare edges of Q, then there is only one pocket. Therefore, Qmust be a convex polygon, and Tconsists of all sides of Qbut one. A compatible triangulation verifying ii) is easily obtained now, as shown in Figure 5. Let us now consider the other possible case, in which the tree has vertices inside the polygon Q. Lemma 3. Let Qbe a simple polygon with vertices q1, . . . , qk,k≥3,and let Tbe a geometric tree having as set of vertices {q1, . . . , qk}∪{p1, . . . , ps}, where the pi’s are interior to Q, in such a way that the edges of the tree are in the interior of Q, and all the pockets are convex. See Figure 6. Then: i) If Tis a star, then s= 1 and c(T) = 2. ii) If Tis not a star, then c(T) = 1. Proof. i) Notice that since all the pockets are simple polygons, the leaves of Tmust be vertices of Q. Then, if Tis a star, the only interior point is the center of the star and the union of Qand Tis the only compatible triangulation of Q, and has two components. ii) If Tis not a star every T-compatible triangulation ∆ of Qwill consist of 2s+k−2 triangles. Let us prove ii) by induction on this number of triangles. If 2s+k−2 = 4, the 8 Q T qi qj Figure 6: A tree with convex pockets and some vertices inside Q. base case, the only possibility is shown in Figure 7 (left), and the statement of the lemma holds. As a first case, let us assume that some diagonal d=qiqjis an edge of T. Then, d divides Qinto two subpolygons Q1and Q2. If both Q1and Q2contain points in their interior, as dis an edge of both Q1and Q2, neither the subtree T1placed in Q1nor the subtree T2placed in Q2can be a star, and the result follows by induction. On the contrary, if for example Q1does not contain points in its interior, we can triangulate the points in Q2, using the hypothesis induction, with only one red component A2. By the previous lemma, we can triangulate Q1with two components: A1, containing qi, and B1, containing qj. Since the points qiand qjare in Q1∩Q2, all the points can be connected using red edges, and therefore there is only one red component. The second and last case happens when Tdoes not contain diagonals of Qas edges. Then, let us consider an arbitrary interior point p1. Since Tis not a star, p1belongs to a convex pocket Pithat is not a triangle. Suppose pocket Piis defined by two consecutive points qiand qi+1 of Qand that the point on Pinext to qi+1 is p(see Figure 7, center and right). We can suppose, changing the orientation of Qif necessary, that p16=p. Then, if p∈Q, it has to be the point qi+2. In this case, the tree T0=T−qi+1qi+2 is contained in the polygon Q0obtained by skipping the point qi+1. Therefore, if T0is not a star, by induction we can build a T0-compatible triangulation ∆0with only one red component. Adding to ∆0the black edge qi+1qi+2 and the red edge qiqi+1, we obtain a T-compatible triangulation ∆ of Qhaving only one component. On the contrary, if T0 is a star, there is only one T0-compatible triangulation ∆0. In this case a T-compatible triangulation ∆ is obtained by removing the edge qiqi+2 from ∆0, and inserting the red edges qiqi+1,p1qi+1 and the black edge qi+1qi+2. Finally, if p /∈Q, let us consider the polygon Q0=q1, . . . , qi, p, qi+1, qi+2, . . .. Then, Q0 contains T, has one triangle less than Qand contains the interior point p1, so the result follows by induction. 9 Definition 3. Let ∆be a T-compatible triangulation of the interior of Q. A sequence of adjacent triangles B=F1, F2, . . . , Flof ∆, is called a separating band if it satisfies the following conditions: 1) Each triangle Fihas a black edge eiin common with Fi+1,i= 1,...l−1. 2) Additionally, F1contains another black edge e0and Flcontains another black edge el, and these two edges e0and elare sides of Q. Q B→ e0F1 F2 S+ S− P− P+ el ui uj=uj0 ui0 R ++ ++ ++ + − −− −−−− S− Figure 15: A separating band Bof a compatible triangulation. A separating band in a triangulation of a tree inside a polygon is shown in Figure 15. By construction, the separating band B=F1, F2, . . . , Flhas l+ 1 black edges and lred edges given by the constituent triangles. Let us describe some elementary properties of a separating band. First of all, we give a rule for assigning a + or −sign to each triangle in the band. We start by giving sign + to F1. In the generic step, let us assume that signs have been defined for F1, . . . , Fi. Then, if the common vertex between ei−1and eiis the same as the common vertex between eiand ei+1, we assign to Fi+1 the same sign as Fi, while we assign the opposite sign if those common vertices are different. By construction all the red edges of the positive triangles form a path P+, and similarly a red path P−with the red edges of the negative triangles. These two paths together with the edges e0and elform a simple polygon, the boundary of the band. When all the triangles have the same sign (say +) or when the sequence is formed by only one triangle with two black edges on Q, then we take P−as a path of length 0 formed by the unique vertex of the band not in P+. A separating band Bpartitions the vertices of ∆ into two sets (the sides of the band), those that lie in the same zone than the points of P+, which will denote it by S+, and those on the side of the points of P−, which we denoted by S−. As there are no red edges between S+and S−, any component Ciof ∆ is completely included in one of the two sides of a separating band. Let us call spine of the band the black path formed by first the edge e0, then the common edges of consecutive triangles having different sign, and finally edge el. The spine is a path that alternates between points of each side. The following lemma makes clear why separating bands are a useful tool. Lemma 8. Let ∆be a T-compatible triangulation of the interior of Q, and let e=vivj be an edge of T, such that viand vjare in different red components Ciand Cjof ∆, respectively. Let Sij be the set of edges of ∆with an endpoint in Ciand the other in Cj. Then, either one of the components, say Ci, consists of only one vertex vi, and Sij 16 is formed by all the edges incident to vi, or Sij consists of the black edges in a separating band of ∆. Proof. Let us label the points of Sas type iwhen they belong to the component Ciof ∆. Any edge linking in ∆ points with different labels must belong to T, and since Tis a tree, every triangle of ∆ has at least two vertices with the same label. Therefore, given any triangle v1v2v3of ∆, if v1has label i1different from the label i2of v2, then the label of v3 must be either i1or i2, being v2v3black and v1v3red in the first case, and v1v3black and v2v3red in the second case. The edge e=vivjbelongs to at least one triangle F1of ∆. The other two edges of F1cannot be both black because Tis a tree, and cannot be both red either because vi and vjare in different red components. Thus, if v0is the other vertex of F1, one of the edges viv0and vjv0has to be red, and the other one black. Suppose, for example, that the black edge is e1=viv0, and let us give sign + to this triangle. If e1is not an edge of Q, it belongs to other triangle F2with another additional black edge e2. If this edge e2is not in Q, we can again obtain a new triangle F3containing e2and another black edge e3, and so on. In the same way that we have described after the definition of separating bands, we assign to Fi+1 same or the opposite sign than Fi, depending on whether the common vertex between eiand ei+1 is the same or different to the previous common vertex. This process of incrementally gluing triangles can finish only in two ways: Either in the last explored triangle Flthe last edge elis on Q, in which case triangle Flcan be glued only with Fl−1, or Flcan be glued with F1by the edge el. No other option is possible because a triangle with two black edges can be glued to at most two other triangles. Let us analyze first the case in which after Flwe encounter F1again. This case may happen when F1, . . . , Flare all the triangles placed around the interior vertex vi; in fact, it is the only situation in which it can arise: If in the cyclic sequence F1, . . . , Fl, F1there are triangles with different signs, consider the edges ei1, ei2,...eisadjacent to consecutive triangles with different sign, with the arithmetic of indices modulo s, so that eis+1 =ei1. Let us consider a visit of these triangles in the order, F1, . . . , Fl, F1, and let us orient the edges eirfrom the vertex in Cito the vertex in Cj, if eirwhen crossing the edge means going from a positive triangle to a negative triangle, and in the opposite direction for the reverse transition of signs. Since eirand eir+1 share a vertex and alternately visit points from one component and the other, the edges ei1, ei2,...eishave to form a cycle, contradicting that Tis a tree. Notice that if viis a vertex of Q, some of the triangles adjacent to vihave only one neighbor, therefore this cyclic case cannot happen if the initial edge e=vivjbelongs to Q. Let us conclude with the case in which the incremental gluing of triangles finishes because elis an edge of Q. If the initial edge e=vivjis also an edge of Q, then the sequence B=F1, . . . , Flis clearly a separating band, and since all the vertices of Cihave to be on one side, S+or S−, of the band, and the vertices of Cjon the other side, there are no other black edges connecting points of Ciand Cj. If the initial edge e=vivjdoes not belong to Q, we can repeat the process starting with the last edge el, which is on Q, and obtain in this way a separating band. From the previous lemma, we can infer that a T-compatible triangulation ∆ can contain two types of red components, those formed by exactly one isolated vertex placed inside Q, and those containing vertices of Q, separated one from each other by separating bands. We will call these latter components the big components of ∆ (despite the name, 17 notice that a big component might consist of only one vertex of Q). We present next two more lemmas that we are using in the forthcoming sections. Let ∆ be a triangulation containing the geometric tree T, and let vbe a vertex of Thaving degree at least 2 (in T). Suppose that eis a red edge incident to v, and that rotating earound vthe first black edges we find are b1and b2, clockwise and counterclockwise, respectively. We will say that point vis convex with respect to edge eif the clockwise angle from b2to b1is < π. Lemma 9. Let B=F1, F2, . . . , Flbe a separating band of ∆. Suppose that the path P− consists of the vertices u1, u2, . . . , um, and that not all of them are on Q. Then, there are two vertices uiand uj,i < j, of P−satisfying: i) For i<k<j,ukis not on Qand all the edges of Tincident to ukare in the band B. ii) If uiis not on Q, then it is convex with respect to uiui+1, and if ujis not on Q, then it is convex with respect to uj−1uj. iii) If uiand ujare both on Q, then they are not consecutive on P−. See Figure 15. An equivalent statement can be formulated taking the path P+instead of the path P−. Proof. Since u1and umbelong to Qand not all the vertices of P−are on Q, there are at least two nonconsecutive vertices of P−,ui0and uj0, such that i0< j0, they are on Qand none of the vertices of P−between them belongs to Q. Let Rbe the region defined by the two polygonal paths from ui0to uj0, one on Qand the other one on P−. See Figure 15. Then, consider the subsequence ui0, ui1, . . . , uis=uj0beginning in ui0, ending in uj0, consisting of all the intermediate vertices uikthat are incident to some edge of Tinside R. Note that scan be 1, and this subsequence consists of only two vertices, ui0and uj0. Let us visit these vertices uikof P−in order from 1 to s−1, and create a pre-label C or N before each such vertex uik, according to whether the vertex is convex or non-convex with respect to edge uik−1uik, and create as well a post-label C or N after each vertex, according to whether it is convex or non-convex with respect to edge uikuik+1. By convenience, let us place a label C after vertex ui0and before uj0. Observe that, when P−is traversed, if a vertex uikis not convex with respect to edge uik−1uik, then it has to be convex with respect to edge uikuik+1. Therefore, we are necessarily finding two consecutive vertices uikand uik+1 (in the subsequence ui0, ui1,...uj0), such that the pattern of labels placed after uikand before uik+1 is C-C. Taking these two last vertices as ujand uj, clearly they satisfy i), ii) and iii). Lemma 10. Let Bbe a separating band of a T-compatible triangulation ∆, and let us suppose that not all the vertices of P−are on Q. Then, there is a pocket Piwith at least four vertices, with red side qiqi+1 ∈S−, such that either Picontains an isolated convex vertex in P+, or there is a zigzag of Piwith all its convex vertices in P+. Proof. Figure 16 shows an example of the situation described in the statement, in which the zigzag starting at viand finishing at vj−1is contained in the pocket Pidefined by the red edge qiqi+1. 18 Q S+ T P+ F1 el ui uj vivi+1 Pi S− P− ui+1 B→vj−1 qi qi+1 Figure 16: Illustration of Lemma 10. As a first observation for the proof, let us consider any arbitrary vertex ukof P−, yet different from the last one. Let e0 kbe the red edge ukuk+1, let Fkbe the triangle of B containing e0 k, and let ekbe the black edge of Fkwith endpoint uk. Then, the endpoint ek different from ukmust be a vertex vk∈P+. Moreover, if Pkis a pocket of Tcontaining a set of consecutive triangles of B,Fk, . . . , Fk+k0, with an edge on P−and sharing vertex vk, then vkis convex in that pocket, because it is a vertex of all these triangles. Now, due to Lemma 9, there are two vertices uiand uj,i < j on P−satisfying the conditions i), ii) and iii) of that lemma. Suppose that uiand ujare not on Q. Hence, uiis convex with respect to the following red edge e0 i=uiui+1,ujis convex with respect to its predecessor edge uj−1ujand all other vertices in P−between uiand ujcannot have any incident edge placed outside of B. See Figure 16. In the pocket Pithat contains the edge e0 i, clockwise after the convex vertex ui, comes the convex vertex vi, then vertex ui+1, which in its turn is followed by another vertex v0 i that may coincide with vior may be vertex vi+1. Again after v0 icomes vertex ui+2, which is followed by another vertex of P+, and so on. See Figure 16. Consider this sequence of vertices ui, vi, ui+1, v0 i, . . . , v0 j−1, uj. Notice that in this sequence vertices of P−and P+ appear intertwined, and that the vertices of P+are convex in Pi. Therefore, since ujhas to be convex in Pi, the sequence contains a first vertex ulof P−(different from ui) that is convex in Pi. Then, if l=i+ 1, viis an isolated convex vertex of Pi, and if l6=i+ 1 (lcan be j), the sequence vi, ui+1, . . . , vl−1is a zigzag of Piwith all its convex vertices on P+. Moreover, Pihas at least four vertices: qi, qi+1, uiand uj. Finally, the argument is very similar for the other cases –uior ujor both being on Q– because these vertices are convex in any pocket (property (W) of the vertices of Q). 2.6 The two main types of trees Throughout this section we consider a geometric tree Tincluded in a polygon Q, and assume that we are in the most general situation, this is, that all the pockets of Tare 19 Figure 17: Examples of trees with Q-convex pockets, having one and two components (left and right, respectively). weakly simple polygons, which in some case may be proper simple polygons. For simplicity we are calling them just pockets in all cases. Proposition 1. Let Tbe a given geometric tree included in a polygon Q. If all the pockets of Tare Q-convex, then we can obtain a T-compatible triangulation of the interior of Q having either one or two red components. Proof. The result is a direct consequence of Lemmas 2, 3, and 6. We can use Lemma 6 to transform each non-convex pocket into several convex pockets, hence obtaining a tree with convex pockets placed inside a polygon Q. If all the vertices of Tare placed on Qor if T is a star, by Lemma 2 we can triangulate the interior of Qobtaining two red components. Otherwise, using Lemma 3, we obtain only one red component. Figure 17 shows two geometric trees with Q-convex pockets, and corresponding compatible triangulations for these examples with the minimum number of components. The following corollary tells us when two red components are unavoidable in any T- compatible triangulation, for trees Twith Q-convex pockets: Corollary 1. Let Tbe a given geometric tree included in a polygon Q. Suppose that all the pockets of Tare Q-convex and that Tis not a star. Then: i) If Tcontains a vertex v, not placed on Q, and convex in all its incident pockets, then there is a T-compatible triangulation with only one red component. ii) Otherwise, any T-compatible triangulation has at least two red components. Furthermore, given any edge e=vivjof T, there is a T-compatible triangulation with two red components, one of them containing vi, and the other one containing vj. Proof. i) We transform the pockets of Qinto convex pockets of a new polygon Q0using Lemma 6. Then, vertex vis in the interior of Q0. Therefore, the result follows from Lemma 3. ii) If Tdoes not contain any vertex vsatisfying condition i), once we have obtained the transformation of pockets using Lemma 6, we obtain a T-compatible triangulation with two red components by Lemma 2, as claimed. In fact, we should also prove that if aQ-convex pocket is not triangulated decomposing this pocket into convex pockets in the usual way, then still we have two or more components, yet this result is easily obtained by induction. 20 Figure 18: Base of the induction in Proposition 2. Proposition 2. Let Tbe a given geometric tree included in a polygon Q, having at least one ordinary pocket. Then, we can obtain a T-compatible triangulation ∆of the interior of Q, such that ∆only has one big red component, and all the other components, if any, consist of isolated interior vertices. Proof. If Thas Q-convex pockets we can transform them as indicated in Lemma 6. Therefore, we can assume hereafter that all the pockets of Tare either convex or ordinary pockets. We are proving by induction that it is possible to triangulate the pockets of Tin such a way that all the vertices placed on Qare in the same red component. In this way, we are gluing all the big red components, because, by Lemma 8, any big component has a vertex on Q. For n= 4, Figure 18 shows the two only possibilities for a tree to have ordinary pockets and their corresponding triangulations. Let us consider first the case in which there is an edge e=v1v2of Tsuch that v1and v2are nonconsecutive vertices of Q. This edge divides Qinto two subpolygons Q1and Q2 enclosing two subtrees T1and T2, such that T=T1∪T2and T1∩T2=e. Since Tcontains at least one ordinary pocket, at least one of the trees T1and T2has an ordinary pocket. If both subtrees T1and T2contain ordinary pockets, then the result follows by induction. If one of the trees, say T1, contains an ordinary pocket and the pockets of T2are convex, then by induction all the vertices of Q1(including viand vj) can be placed in the same red component. By Lemma 2, all the vertices of Q2can be placed in two components, one containing vi, the other one containing vj. Therefore, in the T-compatible triangulation all the vertices of Qwill be in the same red component, and we are done. As a second possibility, let us consider the case in which there are no edges of T linking nonconsecutive points of Q, but Thas a convex pocket Pi, with red side qiqi+1, which contains another vertex qjof Q. If qj=qi+2, then necessarily qi+1 is leaf of T and we can apply induction in the subtree T0=T−qi+1qi+2 enclosed in the polygon Q0=q1, q2, . . . , qi, qi+2, . . .. Adding to this triangulation of Q0the red edge qiqi+1 and the black edge qi+1qi+2, we obtain a triangulation of Qwith all the vertices of Qin the same red component. The same argument applies if qj=qi−1. Suppose now that qj6=qi−1, qi+2, and that i<j. In this situation we consider the subpolygons Q1=q1, . . . , qi, qj, qj+1, . . . , q1 and Q2=qj, qi+1, qi+2, . . . , qj, enclosing two subtrees T1,T2, having in common only the point qj, with T=T1∪T2(see Figure 19, left). As in the previous case, if both T1and T2 contain ordinary pockets, then the result follows by induction on T1and T2(enclosed in Q1and Q2, respectively). If the assumption doesn’t hold, we have to consider the case in which T1contains an ordinary pocket and T2contains only convex pockets. Now, all the vertices of Q1can be placed in one red component, and observe that the vertex vfollowing qi+1 in the pocket Picannot be a vertex of Q2(otherwise, qi+1vwould be a diagonal of Q). Since all the pockets incident to vmust be convex, by Corollary 1 the vertices of T2 can also be placed in one red component, except if T2is a star centered at v. But in this last case we can connect all the leaves of T2, including qi+1 and qj, and hence the result 21 follows again. Q1 Q2 qiqi+1 T1 T2 Pi Q v C− C+ qj v Q Figure 19: Illustration of cases for Proposition 2. As a third and last case, suppose that Tneither contains an edge linking two nonconsecutive points of Qnor any convex pocket with at least three vertices of Q. Using Lemmas 5 and 7, we can built a T-compatible triangulation ∆ in which all the ordinary pockets are triangulated in such a way that all the isolated convex vertices and all the zigzags (this is, at least one convex vertex of each zigzag) are linked by some diagonal. Suppose that not all the vertices of Qare in the same red component of ∆. Therefore, there is a separating band B=F1, . . . , Flsuch that each component is placed either in S+ or in S−. In particular we have a red component C+containing the vertices of the path P+of red edges and another red component C−containing the vertices of P−. Now, suppose that not all the vertices of P−are on Q. Then, by Lemma 10, there is a pocket Piplaced on S−that contains either an isolated convex vertex in P+or all the convex vertices of a zigzag in P+. Now, since in each ordinary pocket all the zigzags and all the isolated convex vertices are endpoints of red edges, the only possibility for Piis to be a convex pocket: Pi∩S+consists of only one vertex v, and Pihas been triangulated such that it contains two red components, one of them consisting only of the point v. In addition, notice that Pimust contain at least four vertices, and as Picannot contain three points of Q,vmust be an interior vertex. See Figure 19 (right). We can now change the triangulation of Piin such a way that vlies in a bigger red component. In this way, we obtain new red components and new separating bands only retriangulating a convex pocket. Notice that all the vertices belonging to the component C+, are in a new component C0 +containing at least two more vertices. Again C0 +can be separated from another component C0 −by a separating band B0, and if not all the vertices of P0 −are on Q, we can build once again a new bigger red component C00 +. We can continue doing the preceding process that increases the size of the component C+, until either only one big component is obtained, or we have obtained a separating band Bsuch that all the vertices of P−are on Q. But this last case can never happen, because then not all the vertices of P+would be on Qand, therefore, again by Lemma 10, there would be a convex pocket Picontaining one vertex vin S−⊂Qand the remaining ones in S+, that is, a pocket with at least three vertices of Q, which is not possible. Notice that the method of the proof provides implicitly an algorithm for obtaining a compatible triangulation having all the vertices of Qin the same red component. The 22 complexity of the algorithm depends on the specific way of computing and updating the red components of the triangulations, but even with a naive approach for these steps the complexity of the method is O(n2). 2.7 Proof of Theorem 1 Let us call ordinary trees those trees inside a polygon Qthat have some ordinary pocket. We have seen that for ordinary trees T, there is always a T-compatible triangulation ∆ such that all the vertices of Qare in the same red component of ∆−T, the big component, and that other component, if any, would consist each of a single isolated vertex. We study closely here the number of isolated vertices that a T-compatible triangulation may admit as components in the red graph. Notice first that for some trees components consisting of only one vertex are unavoidable. Figures 20 and 21 show two examples of that situation. In the tree of Figure 20 there are several totally isolated vertices, i.e., vertices of Tnot “seeing” any other vertex of T. Therefore, there are no red edges incident to these vertices in any compatible triangulation. In Figure 21 we show a tree in which either vertex v1or vertex v2have to be isolated in any compatible triangulation ∆, in spite of the fact that each of them can see some vertex of T. u v1 w1 v2 w2 v3 w3 Figure 20: A tree with many totally isolated vertices. Observe that, given an ordinary tree Tand a T-compatible triangulation ∆ with only a big component, each isolated vertex uiof the red graph must be in the interior of Q; therefore, uimust be incident to at least three edges of T. Edges incident to an isolated vertex uiare different from edges incident to any other isolated vertex uj, because if uiuj were an edge of Tthis edge would have to belong to a triangle of ∆ with at least a red side, contradicting that both uiand ujare isolated. Therefore, the number of isolated vertices is at most (n−1 3). In fact, we can slightly improve on this upper bound. To that goal, let us see first that we can assume that Tsatisfies the following property: 23 v1v2 Figure 21: Either v1or v2has to be isolated in any compatible triangulation. Property ( c W): For any two adjacent edges uv and uw of T, if the geometric triangle uvw contains some vertices v0 1, . . . , v0 k, then not all of them are leaves of Tadjacent to u. If property ( c W) is not satisfied, and hence triangle uvw contains only the leaves v0 1, v0 2, . . . , v0 kof T, with k≥1 and each uv0 ibeing an edge of T, consider the tree T0 obtained by the removal of v0 1, v0 2, . . . , v0 kfrom T. Given a T0-compatible triangulation ∆0 of T0, we can insert in ∆0the edges uv0 iwithout producing any crossing. Therefore, we can complete ∆0to a T-compatible triangulation ∆ of Twith the same number of isolated points as ∆0, because vertices v0 icannot be isolated once added. Therefore, any upper bound for the minimum number of isolated points for trees satisfying ( c W) is also valid for arbitrary trees. As a second step, let us see that we can increase the number of vertices of the big component by doing the following process: Suppose that ∆ is a T-compatible triangulation having one big component C, and u is a vertex not in C. Let v1, . . . , vkbe the clockwise neighbors of uin T. Notice that k≥3 and that uis inside Q. We can also assume that Tis not a star. Therefore, some of the triangles uvivi+1 has an adjacent triangle vivi+1wi. Then, if the quadrilateral uvivi+1wiis convex, we can replace the red edge vivi+1 by the red edge uwi. Notice that the vertices v1, . . . , vk, v1form a red cycle and, hence, when the edge vivi+1 is removed, the red components do not change, and then, adding the edge uwi, vertex ubecomes part of the big component C. We are now ready for proving the first claim in Theorem 1: Let Tbe a geometric tree. Then there is a T-compatible triangulation ∆0such that ∆0−T contains at most n−3 4isolated vertices, in addition to one large component. Proof. Let Qbe the boundary of the convex hull of T. If Tis Q-convex, then, since there is a triangulation with one or two components, the maximum number of isolated vertices is 1. If Tis an ordinary tree, let ∆ be a triangulation containing all the vertices of Qin one component, and let ∆0be the triangulation obtained from Qfollowing the process described in the paragraph above, preceding the claim. 24 Leu ube an isolated vertex in ∆0, and let v1, . . . , vkbe its neighbors in T. At least one triangle uvivi+1 has an adjacent triangle vivi+1wi, and the quadrilateral uvivi+1wiis not convex. Then, either the ray −−−→ uvi+1 hits first the segment viwi, or the ray −→ uvihits first the segment vi+1wi. Assume that we are the first case: we will say that wiis clockwise in relation to uvivi+1. Observe that i) Vertex vi+1 does not belong to Q, because the clockwise angle between uvi+1 and vi+1wiis greater than π. Therefore, the triangle uvi+1vi+2 has an adjacent triangle vi+1vi+2wi+1. ii) Vertex wicannot coincide with vertex vi+2, because then property ( c W) is not satisfied. Therefore, since the quadrilateral uvi+1vi+2wi+1 cannot be convex, the ray −−−→ uvi+2 hits first the segment vi+1wi+1, and, therefore, again wi+1 is clockwise in relation to uvi+1vi+2. Repeating the same argument, we will find that, for i= 1, . . . , k, the triangle uvivi+1 has an adjacent triangle vivi+1wi, with wibeing clockwise in relation to uvivi+1, i.e., the ray −−−→ uvi+1 hits first the segment viwi, and therefore, in the tree T, clockwise around vi+1, after the edge uvi+1 comes an edge forming an angle greater than π(or vi+1 is a leaf of T). Let us call such an isolated vertex a clockwise isolated vertex of ∆0. See Figure 22. Notice that edges uvihave to be black but edges viwican be red or black. Similarly, in the second case, −→ uvihits first the edge vi+1wi, all the triangles have an adjacent triangle, and in the tree T, counterclockwise around vi, after the edge uvicomes an edge forming an angle greater than π. Let us call such an isolated vertex a counterclockwise isolated vertex of ∆0. See Figure 22. u v1 v3 v2 w1 w2 w3 u v1 v2 v3 v4 w2 w1 w4 w3 Figure 22: Clockwise and counterclockwise isolated vertices in a triangulation ∆0. Let us now suppose that in ∆0the isolated vertices uand u0have a common neighbor viin T, this is, uviand u0viare edges of T. Only two consecutive edges of Taround vi can form an angle greater than π. Therefore, one among uand u0has to be clockwise isolated, say u, and the other one, u0, counterclockwise isolated. See Figure 23 left. Let us denote the clockwise neighbors of uby vi, vi+1, . . . and the clockwise neighbors of u0by v0 i=vi, v0 i+1, . . .. Since ray −→ uvifirst has to cut the edge vi−1wi−1, then, ray −−→ u0vihas to enter first into either the triangle uvivi−1, or into vivi−1wi−1, hitting first edge vi−1wi−1 or edge uvi−1instead of edge v0 i+1w0 i. Therefore, this situation is impossible except in the case that wi−1=v0 i+1 and w0 i=vi−1; this last situation is shown in Figure 23, right. In this case, edge w0 iwi−1belongs to two triangles of ∆0, namely viw0 iwi−1and w0 iwi−1w. Consider the polygon P=w0 iwwi−1u0viu. In this polygon, the diagonal w0 ivican be deleted 25