Transforming Triangulations on Nonplanar Surfaces

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. SIAM J. DISCRETE MATH.c 2010 Society for Industrial and Applied Mathematics Vol. 24, No. 3, pp. 821–840 TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES∗ C. CORT´ ES†,C.I.GRIMA †,F.HURTADO ‡,A.M ´ ARQUEZ†,F.SANTOS §,AND J. VALENZUELA† Abstract. We consider whether any two triangulations of a polygon or a point set on a nonplanar surface with a given metric can be transformed into each other by a sequence of edge flips. The answer is negative in general with some remarkable exceptions, such as polygons on the cylinder, and on the flat torus, and certain configurations of points on the cylinder. Key words. graph of triangulations, triangulations on surfaces, triangulations of polygons, edge flip AMS subject classifications. 68U05, 52C99, 65D18, 68R10 DOI. 10.1137/070697987 1. Introduction. Most of the problems considered so far in computational geometry are restricted to the plane, or to the Euclidean 3-space. However, in many applications it is necessary to deal with input data that lies on a surface rather than in the plane. Recently, some works have been focused on solving some of the problems arising in those cases (cf. [8, 13, 16]). This paper is in this category, studying the graph of triangulations of a polygon on a surface. Partitioning geometric domains into simpler pieces, such as triangles, is a common strategy to several fields, the finite element method being a most relevant example. In particular, the triangulation of polygons is an intermediate step in many algorithms in the area of computational geometry. In many cases, we need to obtain not only a triangulation of a given region but also a “good” one. Some examples of this assertion can be found when it is desired to improve the quality of a graphic representation or to find a “nice” mesh on a given surface in order to apply finite element methods. When the quality of the triangulation with respect to some criterion is considered, and no direct method for obtaining the optimal triangulation is known, it is natural to perform operations that allow local improvements. The best-known method is the edge flip: when two triangles form a convex quadrilateral, their common edge is replaced by the other diagonal of the quadrilateral [2, 6]. This local transformation, introduced by Lawson in [12], can be combined if necessary with methods such as simulated annealing to escape local optima [7, 11] and has also been used for the purposes of enumeration [1]. It also admits several variations [17, 18]. Regarding the local operation we have just described, a basic issue is whether any two triangulations of a domain Dcan ∗Received by the editors July 23, 2007; accepted for publication (in revised form) May 17, 2010; published electronically July 29, 2010. http://www.siam.org/journals/sidma/24-3/69798.html †Dept. Matem´atica Aplicada I, Univ. de Sevilla, Spain ([email protected], [email protected], [email protected], [email protected]). The research of these authors was partially supported by projects MTM2008-05866C03-01 and P06-FQM-01649. ‡Dept. Matem´atica Aplicada I, Univ. Polit´ecnica de Catalunya, Spain ([email protected]). The research of this author was partially supported by projects MICINN MTM2009-07242 and Gen. Cat. 2009SGR1040. §Dept. Matem´aticas, Estad´ıstica y Computaci´on, Univ. de Cantabria, Spain ([email protected]). The research of this author was partially supported by MTM2008-04699-C03-02. 821 Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 822 CORT´ ES, GRIMA, HURTADO, M ´ ARQUEZ, SANTOS, VALENZUELA be transformed into each other by means of a sequence of flips. If we define the triangulation graph of Das that graph TG(D) having as nodes the triangulations of D, with adjacencies corresponding to edge flips, then the above question becomes obviously whether TG(D) is a connected graph or not. It is known that the graph of triangulations of a planar simple polygon or a point set with nvertices is connected and its diameter is O(n2), which is tight [5]. It is worth mentioning that even the case of a convex n-gon Phas been thoroughly studied because TG(P) is isomorphic to the rotation graph of binary trees with n−2internal nodes [10, 19]. On the sphere, the situation is essentially the same as in the plane. In this work we study the connectivity of the triangulation graph for simple polygons and point sets lying on surfaces. Regarding polygons, we prove that for the cylinder and the torus with their flat metrics the graph is always connected (if nonempty). For general surfaces and metrics the situation is usually the opposite. Even worse, for point sets only certain configurations on the cylinder have a connected graph of triangulations. At this point it is convenient to clarify that with the general purpose of extending computational geometry to surfaces, it is necessary to “translate” some of the elements that usually appear in the plane to the surfaces; in our case, we need to know how to join a pair of points (in other words, how to translate the concept of segment); it is known that, in general, there are infinitely many geodesics joining two points but usually only one with the minimal length (see [4]). Thus, following the cited works [8, 13, 16] and others, this unique minimal geodesic joining a pair of points on a surface will be called the segment defined by that pair of points. In what follows, only segments between pairs of points will be considered. Equally some words must be said about the surfaces, or, more concretely, about the metric, that we are considering here. In general, we will study the case of the locally Euclidean surfaces (those surfaces isometric to the plane in sufficiently small regions). These surfaces have two advantages; on one hand, they are general enough in order to model many practical cases or approximate some other metrics, and, on the other, they have an easy representation, as we will see in the next section. Nevertheless, in section 3 the results are presented in a more general context because we do not need the flat representation of the locally Euclidean surfaces (although an alternative proof of the main result of this section is presented later in the context of locally Euclidean surfaces). The paper is organized as follows. In section 2 we give definitions and preliminary results, and we establish the notation that will be used throughout this paper. Section 3 shows one of the main results of this paper, which is that in every compact connected surface it is always possible to find a metric that admits polygons and point sets with nonconnected graphs of triangulations. Section 4 focuses on the connectivity of the graph of triangulations for both polygons and point sets on the locally Euclidean surfaces. We conclude in section 5 with some comments and open problems. 2. Preliminaries. As is known, many practical problems cannot be modeled by planar situations, and other surfaces are required. When we meet phenomena in which the same configuration of generating points appears in cycles, we may analyze them with the aid of a point configuration on the cylinder or the torus. These are two well-known surfaces since, together with the twisted cylinder (or infinite M¨obius strip) and the Klein bottle, they easily admit quotient metrics that make them locally Euclidean. With these metrics, the graph of triangulations of a polygon both on the Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 823 cylinder and on the torus is connected, although this fact does not hold on the other two nonorientable surfaces. We start this section summarizing the basic properties of the locally Euclidean surfaces, via their planar representation. A more complete study of them can be found in [15]. 2.1. Locally Euclidean surfaces. A 2-dimensional locally Euclidean surface is a surface which is isometric with the plane in sufficiently small regions. Amotion in the plane is a map that preserves distances between points. The group of motions in the plane is denoted by Mo(R2) and consists of translations, rotations, reflections, and glide reflections. AgroupΓ⊆Mo(R2)issaidtobeuniformly discontinuous if there exists a positive number dsuch that if γis a motion in Γ and Pany point in the plane being γ(P)=P, then the distance between Pand γ(P) is greater than or equal to d. There are five different types of uniformly discontinuous groups of motions of the plane, up to isomorphisms: Types I, II.a, II.b, III.a, and III.b [15]. They can be generated as follows: •Type I is generated by the identity motion. •Type II.a is generated by a translation. •Type II.b is generated by a glide reflection. •Type III.a is generated by two noncollinear translation vectors. •Type III.b is generated by a translation and a glide reflection, the direction of the translation vector being orthogonal to the axis of the glide reflection. Given a group Γ ⊆Mo(R2)andapointPin the plane, the orbit of Pvia Γ, denoted Γ(P), is the set of the successive images of Punder the action of the elements of Γ, that is, Γ(P)={γ(P):γ∈Γ}. For any uniformly discontinuous group of motions Γ ⊆Mo(R2) the following notion of equivalence on points in the plane can be defined: points Aand Bare equivalent if they belong to the same orbit; namely, there exists a motion γ∈Γ such that γ(A)=B. The orbits are then the equivalence classes under this relation. The set of all orbits of R2under the action of Γ is written as R2/Γ and is called the quotient space. The distance between two points (orbits) A=Γ(A)andB=Γ(B)inR2/Γ is defined to be the shortest of the distances |AB|, where Aand Bare points of the plane with Abelonging to Aand Bto B. Every locally Euclidean surface Σ corresponds to a uniformly discontinuous group Γ of motions of the plane so that Σ can be obtained from Γ as the quotient space R2/Γ. Hence there are exactly five types of locally Euclidean surfaces [15]: the plane (Type I), the cylinder (Type II.a), the twisted cylinder (Type II.b), the (flat) torus (Type III.a), and the Klein bottle (Type III.b). Although the term flat torus applies to surfaces generated by any group of motions of Type III.b, we will follow the convention that considers the translations to be orthogonal. If the translations are not orthogonal, then we call the surface so obtained a skew torus. As we will see in section 4.2, this distinction is not trivial and has important consequences on the connectivity of the graph of triangulations. According to the above definitions and results, a point aof the surface defined by a uniformly discontinuous group Γ is specified by an orbit Aof Γ. However, in order to specify a, there is no need to know all points of A; we need only know one point A of A, and then all the others are obtained from Aby applying motions in the given group Γ. Therefore, in order to determine the set of all points of the surface, we need only specify some region of the plane, for example, a polygon, satisfying the following properties: Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 824 CORT´ ES, GRIMA, HURTADO, M ´ ARQUEZ, SANTOS, VALENZUELA 1. The region contains one point from every set of equivalent points of the plane. 2. No interior point of the region is equivalent to any other point of the region; that is, equivalent points of the region can lie only on the boundary. A region in the plane satisfying 1 and 2 is called a fundamental domain,and the set of points on the surface is obtained from this region by identifying or gluing together equivalent points of its boundary. In general, we will use the fundamental domains that are more common in the literature, that is, an infinite band for both the cylinder and the twisted cylinder and a rectangle on the torus and the Klein bottle. In the skew torus it is also usual to consider as a fundamental domain a parallelogram whose sides are parallel to the direction of the translations. In order to fix the points in the examples given in section 4, we will consider an orthogonal reference system in these surfaces which will be centered, for simplicity, in the leftmost side of the band or in the lowest leftmost corner of the rectangle (or parallelogram) considered as the fundamental domain. In the nonorientable case the OX axis will be taken to coincide with one glide reflection axis of Γ. The tesselations of the plane generated by the previous fundamental domains of each surface together with the orbit of a polygon are depicted in Figures 1 and 2. (a) (b) OY OY OX OX Fig. 1.The orbit of a polygon in (a) the cylinder and (b) the twisted cylinder. (a) (b) OY OY OX OX Fig. 2.The orbit of a polygon in (a) the torus and (b) the Klein bottle. 2.2. Triangulations of Euclidean polygons. Flips. AEuclidean polygon in a locally Euclidean surface is a region homeomorphic to a closed disc and whose boundary consists of finitely many geodesic arcs. A Euclidean polygon may be represented Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 825 as a simple planar polygon, although, depending on the election of the fundamental domain, it might not be completely contained in only one of them. From now on, Euclidean polygons will be assumed to be already drawn in the plane. The segment (that is, the minimum geodesic) between two nonconsecutive vertices of a Euclidean polygon is called a diagonal of the polygon. The diagonal uv is said to be admissible if it is contained inside the polygon (Figure 3). uu’ v Fig. 3.Since the nearest copy of ufrom vis u,uand vcannot be matched inside the polygon and the diagonal uv is not admissible. A(metrical) triangulation of a Euclidean polygon is a partition of the polygon into triangular regions (that is, regions homeomorphic to a disc bounded by three segments) by means of admissible diagonals with no intersections except for their ends. Note that we force every face of a triangulation to be triangular instead of considering a maximal set of segments since, despite being equivalent definitions in the plane, this is no longer true in other surfaces, as will be apparent in section 4.2. In the same way, we define triangulations of point sets as a maximal set of noncrossing segments such that each bounded region is triangular. On the contrary, what happens in Euclidean polygons, given a point set the shape of the region triangulated, depends on the position of the points on the surface, and it can be a Euclidean polygon, or a strip bounded by two geodesics, or the whole surface (see [3, 8]). Let {vi,v j,v k}and {vi,v j,v l}be two triangles in a triangulation sharing the diagonal vivj.Byflipping vivjwe mean the operation of removing vivjand replacing it by the other diagonal vkvlif it is admissible in the quadrangle {vi,v k,v j,v l}.The graph of triangulations of a polygon or a point set Pis the graph TG(P) having as nodes the triangulations of P, with adjacencies corresponding to diagonal flips (Figure 4). 3. Graph of triangulations of a polygon on nonplanar surfaces. One expects that metrical triangulations depend strongly on the metric considered since small changes in the metric might turn admissible diagonals into nonadmissible ones and flip performance would be affected. In this section, we define a metric on the sphere that produces polygons and point sets with nonconnected graphs of triangulations. The same idea will be used to extend this result to a general closed connected surface. On the sphere, with its natural metric, geodesics correspond to great circles and the distance between two points is the length of the shortest arc of the great circle joining them (Figure 5), which is unique with the exception of antipodal (or diametriDownloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 826 CORT´ ES, GRIMA, HURTADO, M ´ ARQUEZ, SANTOS, VALENZUELA Fig. 4.The graph of triangulations of a polygon in the plane. Fig. 5.The distance between two points in the sphere is given by the shortest arc of the great circle joining the points. cally opposite) points. A (Euclidean) polygon on the sphere, as in a locally Euclidean surface, is a region homeomorphic to a closed disc and whose boundary consists of finitely many geodesic arcs. Triangulations, flips, and graphs of triangulations of polygons on the sphere are also defined in the same way as they were in the previous section. By using arguments similar to those in [12], it can be established that the graph of triangulations of any polygon on the sphere is connected with this metric. But it is possible to slightly disturb the metric so that this assertion will no longer be true. Lemma 1. There exists a surface Mhomeomorphic to the sphere (in other words, Mis a sphere with a metric other than the Euclidean distance) such that in Mthere exists a Euclidean polygon with a nonconnected graph of triangulations and a point set also with a nonconnected graph of triangulations. Proof. Consider a great circle Cthat divides the sphere into two open hemispheres H1and H2.Letp1,p 2,...,p 6be a sequence of vertices uniformly distributed on C such that the great circles joining (p1,p 4), (p2,p 5), and (p3,p 6) intersect only in two antipodal points nand sin H1and H2, respectively. We move the vertices p1,p 2,...,p 6slightly toward nuntil the arc joining them inside H1is slightly shorter than the one that crosses through H2. Let L=p1,p 2,...,p 6be a closed polygonal chain strictly contained in H1, and let Pbe the polygon bounded by Lwhose interior is the region with a smaller area of the two into which the surface is divided by the polygonal chain. Now, M Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 827 is obtained from the sphere by lifting up a small region around nuntil the distances (considering the metric inherit from R3) between (p1,p 4), (p2,p 5), and (p3,p 6), are enlarged enough to ensure that the diagonals joining them are nonadmissible in P(so those admissible diagonals are exterior to P), but without changing the length of the other diagonals of P(Figure 6(a)). ( a ) p3 p4 p1 p1 p5 p2 p6 p3 p4 p1 p5 p2 p6 ( b ) Fig. 6.A hexagon with two disjoint triangulations in a “mountainous” sphere. After the lifting of the region around n, the length of any geodesic inside H1on M either is increased or remains the same as its length before the lifting. Moreover, the segments (shortest geodesic arcs) joining (p1,p 4), (p2,p 5), and (p3,p 6) are the arcs of the great circles that join those points in H2. Therefore, Padmits only two different triangulations, shown in Figure 6(b), which cannot be transformed into each other by a sequence of flips, and hence, the graph of triangulations of Pis nonconnected. Basically, the same example can be used for point sets by adding a new vertex p7 on s. To complete a triangulation, join p7to all the other vertices to obtain a set S. By construction, it is not possible to perform flips in any of the quadrilaterals having p7as a vertex (the new diagonals are outside the quadrilaterals). So, Shas the two different triangulations of the original polygon P, and no flip is possible in any of those triangulations. Using the previous lemma, the same reasoning can be extended to the remaining closed connected surfaces by using the fact that every closed connected surface is topologically equivalent to a sphere, or a connected sum of tori (handles), or a connected sum of projective planes. Theorem 1. Any closed connected surface Sadmits a metric that allows polygons and point sets whose graphs of (metrical) triangulations are nonconnected. Proof. WecanmodifythesurfaceMdescribed in the proof of Lemma 1 by adding to it as many handles or projective planes as needed in order to obtain a surface homeomorphic to S. By virtue of this fact, and mimicking the argument we followed on the sphere, it is possible to find a metric on each closed and connected surface that allows polygons and point sets with nonconnected graphs of triangulations (see Figure 7). Note that the reasoning used in the proof of Theorem 1 can be easily extended to any kind of surface. 4. Connectivity of the graph of triangulations on locally Euclidean surfaces. As has been said in the introduction, some of the most common and useful surfaces are the locally Euclidean surfaces because of the advantage of their planar Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 828 CORT´ ES, GRIMA, HURTADO, M ´ ARQUEZ, SANTOS, VALENZUELA Fig. 7.The construction of Figure 6on the sphere with two handles. representations. It is interesting to emphasize the different behavior that these surfaces show when we study the graph of triangulations of a polygon: while the graph of triangulations is connected both in the cylinder and in the flat torus, polygons with nonconnected graphs can easily be constructed in the two nonorientable surfaces. The behavior of the graph of triangulations in the torus is remarkable, since that graph is connected for polygons with the metric of the flat torus, but this is not true for the skew torus. On the other hand, the graph of a point set is nonconnected in general, but, as we shall see next, we can describe all the connected components in the case of the cylinder. 4.1. The cylinder. Let a be the vector that generates the cylinder. Given that an orthogonal reference system is the OX axis parallel to a, a geodesic arc is a segment if and only if its vertical projection is smaller than |a|/2. In order to add a new diagonal to a triangulation, a procedure to determine if the geodesic arc joining two vertices it is a segment is to check if its vertical projection is contained inside the vertical projection of a previously existing diagonal (and, therefore, a segment). 4.1.1. Polygons. If the planar copies of a polygon Pon the cylinder are (each of them) strictly contained in vertical bands of length |a|/2, then any internal diagonal is admissible and planar arguments can straightforwardly be used to establish the connectivity of the graph of triangulations [8]. However, although many different proofs are known for planar polygons in the plane, the authors are not aware of any proof that can be adapted for the general case. Actually, it is not even obvious that in this general situation a polygon can always be triangulated; although, in this case, essentially the same ideas as in the plane provide a proof of this fact. Lemma 2. Any Euclidean polygon of n≥4vertices on the cylinder has an admissible diagonal. Hence, any Euclidean polygon on the cylinder is triangulable. Proof. This proof is based on the proof of Meister’s lemma [14], which establishes the same result for simple polygons in the plane. Consider a Euclidean polygon Palready developed in the plane. Let vbe a convex vertex such that the two edges incident on it go upward (recall that a vertex is convex if its interior angle is less than πradians; otherwise, the vertex is reflex ). Let aand b be the vertices adjacent to v(Figure 8). If ab is an admissible diagonal (a segment contained in P), then we have finished. Otherwise, either ab intersects ∂P or it is exterior to P. If ab intersects ∂P, the argument given in [14] can be mimicked: Start sweeping a line from v, keeping it parallel to the line through ab, until it reaches another vertex Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 829 v a b v a b Fig. 8.The segment matching aand bmay or may not determine a bounded triangle. x v a b Fig. 9.vx is an inner diagonal of the polygon. v a b x v' Fig. 10.vvis a diagonal of the polygon. xof P(it must exist since Phas at least four vertices). Then, vx is an admissible diagonal (Figure 9). If ab is exterior to P, consider the vertical ray (half-line) with vas endpoint, and let xbe the first point of the boundary of Pthat it reaches. If xis a vertex, then vx is an admissible diagonal. Otherwise, rotate the ray either to the right or to the left until it intersects another vertex vof P(Figure 10). The vertical projection of vv is contained inside the vertical projection of the diagonal containing x,sovvis an admissible diagonal. The connectivity of the graph of triangulations of a Euclidean polygon on the cylinder is established by the next theorem. As in the plane, three consecutive vertices Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 836 CORT´ ES, GRIMA, HURTADO, M ´ ARQUEZ, SANTOS, VALENZUELA Theorem 4. The graph of triangulations of a polygon on the flat torus is either empty or connected. Proof.LetT1and T2be two triangulations of a polygon Pon the flat torus. Let u be an extreme earable vertex in P, which exists by Lemma 4. By virtue of Lemma 5, T1(resp., T2) can be transformed by a sequence of flips into another triangulation T 1 (resp., T 2) having an ear in u. Therefore, T 1and T 2are connected by the inductive hypothesis using flips. Regarding the connectivity of the graph of triangulations of a point set Sin the flat torus there are three possible situations: 1. If Sis inside a quadrant, then Sis in Euclidean position, and it has a planar behavior [3], so the graph is connected. 2. If a planar copy of Sis inside a vertical (resp., horizontal) strip of width |a|/2 (resp., | b|/2), the situation is equivalent to the cylinder. The graph is connected if and only if the borders of the triangulated region are fixed (section 4.1). 3. In the other case the connectivity of the graph of triangulations is still an open problem. Our conjecture is that this graph is connected. Nevertheless, as we pointed out in section 3, the connectivity of the graph of triangulations is not preserved if the torus is generated by two nonorthogonal translations. In this way, consider the planar representation of a skew torus generated by two translations with vectors forming an angle of arccos 1 5. In order to simplify the coordinates of the vertices, we choose a horizontal unitary vector and the other one with modulo 2√5 5, and hence the height of a fundamental region is one unit. Using the usual reference system, we can draw a hexagon of vertices a(1 2+ε, 3 4), b(1 −ε, 3 4), c(1 + ε 3,1 2), d(1 −ε, 1 4), e(1 2+ε, 1 4), and f(1 2−ε 3,1 2), with ε<1 8. Since the diagonals ad,be,andcf are not admissible, it is not possible to perform flips in either of the two triangulations depicted in Figure 20. ab c d e f ba b c de f b ab babb d eed Fig. 20.The previous hexagon with all the possible segments between its vertices. And, as we have done in section 3, new points can be added to the previous Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 837 construction to obtain a point set with a nonconnected graph of triangulations. We include points g(0,3 4), h(1 4,3 5), i(1 4,2 5), and j(0,1 4), as is shown in Figure 21. The central hexagon (bold lines) still admits only six diagonals, giving rise to only two different triangulations, and the segments of the boundary of the hexagon cannot be flipped. So the graph of triangulations of the set has two connected components. ab c d e f b b c d b ab babb d eed g h i j g j a e f h i g j Fig. 21.It is not possible to carry one of the triangulations of the central polygon into the other by flips. Therefore, the previous example shows (applying a suitable angle transformation if necessary) the following result. Theorem 5. It is possible to find a polygon and a point set on a skew torus such that their graphs of (metrical) triangulations are nonconnected. It is worth pointing out that the previous result leads to another proof of Theorem 1. 4.3. Nonorientable locally Euclidean surfaces. It is easy to embed in the twisted cylinder and in the Klein bottle a polygon whose graph of triangulations is nonconnected. We look for a situation similar to the one used previously for the skew torus (Figure 20)—a hexagon of vertices (in clockwise order) a,b,...,f such that all the diagonals are admissible except for the diagonals (a, d), (b, e), and (c, f). This hexagon has only two triangulations, and it is not possible to perform a flip. Consider the twisted cylinder with the usual coordinate system, and assume a glide reflection with unitary vector. The hexagon of vertices a(1 4+ε, 1 4), b(3 4−ε, 1 4), c(3 4+ε 3,0), d(3 4−ε, −1 4), e(3 4+ε, −1 4), and f(1 4−ε 3,0), with ε< 1 16 , has a nonconnected graph of triangulations (Figure 22). The same construction can be easily obtained on the Klein bottle. A similar study can be extended to the other surfaces obtained as the quotient of the plane over a group of motions (Euclidean 2-orbifolds) if the group contains a glide reflection. In particular, this hexagon can also be embedded into the projective plane with the quotient metric. Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 838 CORT´ ES, GRIMA, HURTADO, M ´ ARQUEZ, SANTOS, VALENZUELA ab c d e f ab c d e f Fig. 22.The segments ad,be,andcf are outside the polygon. By adding only two new points, as Figure 23 shows, the previous example can be extended to a point set with a nonconnected graph of triangulations. Again, as we saw in section 4.2 for the skew torus, the central hexagon has two possible triangulations and no flip is possible inside it. And, since the segments of the boundary of the hexagon cannot be flipped, the two triangulations belong to different connected components. ab c d e f g h ab c d e f g h ab c d e f Fig. 23.The only flips allowed are restricted to the shaded regions. Slightly more complicated is the example given for the Klein bottle (Figure 24), but the reasoning is the same; the segments that form the central hexagon cannot be flipped; hence the set has two disjoint triangulations. 5. Conclusions and open problems. In this paper we have studied the connectivity of the graph of triangulations of polygons and point sets on a surface. We have seen that, in general, this graph is nonconnected. More precisely, we have proven that any surface admits a metric such that there exist a polygon and a point set on that surface (and with that metric) with a nonconnected graph of triangulations. There exist some remarkable exceptions. The first among these, of course, are the plane and the sphere, and then polygons on the cylinder and the flat torus, these surfaces being the only ones to which Lawson’s method [12] to obtain an optimal triangulation could be applied. Nevertheless the practical applications of this method are not clear since we have not found reasonable bounds for the diameter of the graph of triangulations in these surfaces. Some problems are still unsolved. The main question that remains after Theorem 1 is whether it is possible to define a metric in a surface forcing the graph of triangulations of any polygon to be connected, as has been shown for the torus. Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 839 a b c d e f g hi g hi dc b a d a f e b a c d e a f dc a b f d e ih h i g g Fig. 24.It is not possible to carry one of the triangulations of the central polygon into the other by flips. And, concerning the flat torus, the connectivity of the graph is not established if it is associated to triangulations of point sets instead of polygons. REFERENCES [1] D. Avis and K. Fukuda,Reverse search for enumeration, Discrete Appl. Math., 6 (1996), pp. 21–46. [2] M. Bern and D. Eppstein,Mesh generation and optimal triangulation, in Computing in Euclidean Geometry, D. Z. Du and F. K. Hwang, eds., World Scientific, River Edge, NJ, 1992, pp. 23–90. [3] C. Cortes, A. Marquez, and J. Valenzuela,Euclidean position in euclidean 2-orbifolds, Comput. Geom., 27 (2004), pp. 27–41. [4] M. P. do Carmo,Differential Geometry of Curves and Surfaces, Prentice–Hall, Englewood Cliffs, NJ, 1976. [5] M. Noy, F. Hurtado, and J. Urrutia,Flipping edges in triangulations, Discrete Comput. Geom., 22 (1999), pp. 333–346. [6] S. Fortune,Voronoi diagrams and Delaunay triangulations, in Computing in Euclidean Geometry, D. Z. Du and F. K. Hwang, eds., World Scientific, River Edge, NJ, 1992, pp. 193–234. [7] C. D. Gelatt, S. Kirkpatrick, and M. P. Vecchi,Optimization by simulated annealing, Science, 220 (1983), pp. 671–680. [8] C. I. Grima and A. M´ arquez,Computational Geometry on Surfaces, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001. [9] C. I. Grima, A. M´ arquez, and L. Ortega,Anew2d tessellation for angle problems: The polar diagram, Comput. Geom., 34 (2006), pp. 58–74. [10] F. Hurtado and M. Noy,Graph of triangulations of a convex polygon and tree of triangulations, Comput. Geom., 13 (1999), pp. 179–188. [11] P. J. M. Van Laarhoven and E. H. L. Aarts,Simulated Annealing: Theory and Practice, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1987. [12] C. L. Lawson,Transforming triangulations, Discrete Math., 3 (1972), pp. 365–372. [13] M. Maz´ on and T. Recio,Voronoi diagrams on orbifolds, Comput. Geom., 8 (1997), pp. 219–230. Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 840 CORT´ ES, GRIMA, HURTADO, M ´ ARQUEZ, SANTOS, VALENZUELA [14] G. H. Meister,Polygons have ears, Amer. Math. Monthly, 82 (1975), pp. 648–651. [15] V. V. Nikulin and I. R. Shafarevich,Geometries and Groups, Springer Series in Soviet Mathematics, Springer, Berlin, 1987. [16] A. Okabe, B. Boots, and K. Sugihara,Spatial Tesselations. Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, New York, 1992. [17] M. Pocchiola and G. Vegter,Computing the visibility graph via pseudo-triangulations,in Proceedings of the 11th Annual ACM Symposium on Computational Geometry, ACM, New York, 1996, pp. 248–257. [18] F. Santos,Geometric bistellar flips. The setting, the context and a construction,inInternational Congress of Mathematicians, Vol. III, M. Sanz-Sol´e, J. Soria, J. L. Varona, and J. Verdera, eds., European Mathematical Society, Helsinki, Finland, 2006, pp. 931–962. [19] D. D. Sleator, R. E. Tarjan, and W. P. Thurston,Rotations distance, triangulations and hyperbolic geometry, J. Amer. Math. Soc., 1 (1988), pp. 647–682. Downloaded 01/25/16 to 150.214.182.82. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php