cflCopyright by Tiow-Seng Tan, 1993 OPTIMAL TWO-DIMENSIONAL TRIANGULATIONS BY TIOW-SENG TAN B.Sc., National University of Singapore, 1984 M.Sc., National University of Singapore, 1988 THESIS Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 1993 Urbana, Illinois Optimal Two-Dimensional Triangulations Tiow-Seng Tan, Ph.D. Department of Computer Science University of Illinois at Urbana-Champaign, 1993 Professor Herbert Edelsbrunner, Advisor A (geometric) triangulation in the plane is a maximal connected plane graph with straight edges. It is thus a plane graph whose bounded faces are triangles. For a fixed set of vertices, there are, in general, exponentially many ways to form a triangulation. Various criteria related to the geometry of triangles are used to define what one could mean by a triangulation that is optimal over all possibilities. The general problem studied in this thesis is the following: given a finite set S of vertices, possibly with some prescribed edges, how can we choose the rest of the edges to obtain an optimal triangulation? Just to mention an example, we are interested in computing a min-max angle triangulation of S, that is, a triangulation whose maximum angle over all its triangles is the smallest among all triangulations of S. This thesis presents a number of new algorithms to construct optimal triangulations useful in engineering and scientific computations, such as finite element analysis and surface interpolation. All algorithms are the first and, currently, the only ones that construct the defined optimal triangulations in time polynomial in the input size. These main results are described in three parts. First, we develop a new algorithmic technique called the edge-insertion paradigm. It computes for a set of n vertices an optimal triangulation defined by some generic criterion. From this, we deduce that a min-max angle and a max-min height triangulation can be computed in O(n2 log n) time and linear storage, and a min-max slope and a min-max eccentricity triangulation in cubic time and quadratic storage. Second, we show that a min-max length triangulation for a set of n vertices can be computed in quadratic time and storage. Length refers to edge length and is measured by some normed metric such as the Euclidean or any other lp metric. Third, for a given plane graph of n vertices and m non-crossing edges, we prove that there is a set of O(m2n) points so that, for each adjacent pair of points on an edge, there exists a circle passing through the two points that encloses no other points. This implies an efficient way to construct a so-called conforming Delaunay triangulation, which is a Delaunay triangulation that subdivides the given plane graph. These results collectively provide a foundation for further algorithmic studies of optimal triangulations. iii To my parents Tan Bac Hik and Lee Gee Moi, and my wife Chia Joo Joo for their love. iv Acknowledgments Thank you very much--teachers, friends, and family. You in various ways have helped shape this work from beginning to end. It has been one very long, challenging and arduous adventure, and I sincerely appreciate all the help and advice that you have kindly bestowed upon me along the way. To the National University of Singapore, I give thanks for the study leave and the financial support under the Oversea Graduate Scholarship. I certainly have a fruitful and memorable five-year stay at the University of Illinois at Urbana-Champaign. Professor C. L. Liu, I thank you for instilling in me the dating principle in doing research. Your support, guidance and encouragement during the first two years have built up my perseverance in venturing date after date in the subsequent years. Indeed, no results might have been obtained, if not for the experiences learned from failures. My VLS thanks to you, Dave. Professor Douglas West, I thank you for many lessons on proofs. In particular, your first fifty minutes lecture on proof techniques (Math 312) in August 1988 was most enlightening. Your lessons have served as the fundamental preparation in my first theoretical attempt in Spring 1989. Thank you, Doug; I enjoyed your teaching all these years (until I was carried away by other graphical drawings). Professor Herbert Edelsbrunner, thesis advisor and friend, you have been the inspiration to the work in the past four years. Your visions in the area set the beginning of this thesis, and your involvement in working through vague ideas produced building blocks to the work. The journey with you in discrete and computational geometry, and at Urbana, Champaign, Graz, Vienna and Berlin, has been wonderful, exciting, and memorable. Herbert, my multidimensional thanks to you! To the members of the thesis committee, Professor Herbert Edelsbrunner, Professor C. L. Liu, Professor Faisal Saied, Professor Pravin Vaidya, and Professor Douglas West, I thank you all for your service and interests. And, thank you, Herbert Edelsbrunner, Edgar Ramos, and Douglas West, for many suggestions and corrections to parts of this thesis, and, Marshall Bern, Herbert Edelsbrunner, David Eppstein, Scott Mitchell, and Roman Waupotitsch, for our joint work. To past and present members of our research group, Nataraj Akkiraju, Ulrike Axen, Cecil Delfinado, Tamal Dey, Herbert Edelsbrunner, Mike Facello, Klaus Jansen, Sang Ho Lee, Pat Moran, Ernst M"ucke, Edgar Ramos, Nimish Shah, and Roman Waupotitsch, I thank you all for useful meetings, and especially to you, Roman, for sacrificing many fine afternoons to breath chalk dust at DCL 2429. And, Joyce Woodworth, thank you for your help in administrative matters. It was a stressful two months in preparing for the qualifying examination (December 1988- February 1989). To my friends, Ran Libeskind-Hadas, for your inspiration and company in the preparation, and Nany Hasan, for your encouragement and support, and to my wife Joo-Joo, for your forgiveness and quiet acceptance to the bully at home, I thank you all so very much! v To many friends, I thank you for your letters and sweet memories together at UrbanaChampaign. Thank you, Chuah Ban Keat, Lim Pink, Low Chin Kok, Tan Mong Kia, and Toh Sew Kiok, for your many traditional communications. Thank you, Chua Chong Seng and family, Khoo Siau Cheng, Lau Thiam Beng, Uncle Lee Ching Chic, Leong Hon Wai, Lim Kok Yau and family, Low Chin Kok, Whee Keng and Tan Kok Phuang, and Yuen Chung Kwong, for your long distance visits. Thanks you, Poh Lin and Kee Ching Leng, Lee Chia Ling, Lay Chin and Lee Hing Yan, Jessica and Leong Hon Wai, Mui Joo and Ng Pin, and Clover and Kelvin Sung Hsien Ching, for tips on home abroad. And, thank you, Chong Chow Pin, Jocelyn Chong, Chua Teck Joo, Olga Fishman, Foo Soo Mee, Fu Ping, Donald Gillies, Hung Gih Guang, Teck Choo and Stephen Kwek, Dennis Lee, Yen Kim and Lee Meng Chua, Albert Li, Lim Hock Beng, Lim Siew Siew, Esther and Stephen Lim, Lim Swee Boon, Lim Yeow Beng, Loh Mei Yun, Look Jee Loon, Sharon and Low Chin Chau, Mok Chee Liang, Ong Leong Seng, Shi Weiping, Sim Hock Kee, Tan Jin Ho, Carol and Tan Kok Wah, May Ling and Tia Too Seng, and Hsuehling and Yang Der Shung, for wonderful times together. To my family and in-laws, your moral supports have been overwhelming. Thank you all very much! Special thanks to you, Joo Joo, for your love. Tiow Seng Thanksgiving Day, 1992 vi TABLE OF CONTENTS Chapter 1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.1 Two Sample Application Areas : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2 Terminology : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 1.3 Survey of Problems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 1.3.1 Angle Criteria : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 1.3.2 Length Criteria : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 1.3.3 Other Reasonable Criteria : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 1.3.4 Data Dependent Criteria : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 1.3.5 On Steiner Triangulations : : : : : : : : : : : : : : : : : : : : : : : : : : : 13 1.4 Overview of the Thesis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13 2 Some Prior Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 2.1 Plane-Sweep : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.2 Dynamic Programming : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 2.3 Edge-Flip : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 2.4 Delaunay Triangulations and Related Structures : : : : : : : : : : : : : : : : : : 19 2.5 Minimum Length Triangulations : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 3 The Edge Insertion Paradigm : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 3.1 The Paradigm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 3.2 Two Sufficient Conditions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 vii 3.3 The Cake Cutting Lemma : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 3.4 Refinements of the Paradigm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28 3.4.1 Triangulating by Ear Cutting -- Part 1 : : : : : : : : : : : : : : : : : : : 29 3.4.2 Analysis under (I) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 3.4.3 Triangulating by Ear Cutting -- Part 2 : : : : : : : : : : : : : : : : : : : 31 3.4.4 Searching for a Proper Edge : : : : : : : : : : : : : : : : : : : : : : : : : : 33 3.4.5 Analysis under (II) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 3.5 Extensions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 3.6 Discussion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 4 Applications of Edge Insertion : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 4.1 Minimizing the Maximum Angle : : : : : : : : : : : : : : : : : : : : : : : : : : : 40 4.2 Maximizing the Minimum Height : : : : : : : : : : : : : : : : : : : : : : : : : : : 43 4.3 Minimizing the Maximum Slope : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44 4.4 Minimizing the Maximum Eccentricity : : : : : : : : : : : : : : : : : : : : : : : : 47 4.5 Discussion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48 5 Minimizing the Maximum Length : : : : : : : : : : : : : : : : : : : : : : : : : : 51 5.1 The Global Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 53 5.2 The Subgraph Theorem : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 5.3 Preliminaries Results on rng-Polygons : : : : : : : : : : : : : : : : : : : : : : : : 60 5.4 Triangulating Incomplete rng-Polygons : : : : : : : : : : : : : : : : : : : : : : : 63 5.5 A Lemma on Polygon Retriangulation : : : : : : : : : : : : : : : : : : : : : : : : 65 5.6 Triangulating Complete rng-Polygons : : : : : : : : : : : : : : : : : : : : : : : : 67 5.6.1 The Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 68 5.6.2 Triangulating by One 2-Edge : : : : : : : : : : : : : : : : : : : : : : : : : 70 5.6.3 Searching for the Right 2-Edge : : : : : : : : : : : : : : : : : : : : : : : : 73 5.7 Undoing the Simulated Perturbation : : : : : : : : : : : : : : : : : : : : : : : : : 78 5.8 Extension to Normed Metrics : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 79 viii 5.9 Discussion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 82 6 Conforming Delaunay Triangulations : : : : : : : : : : : : : : : : : : : : : : : : 85 6.1 Preliminaries : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86 6.2 The Upper Bound : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89 6.2.1 The Global Idea : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89 6.2.2 The Details : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 90 6.2.3 The Analysis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 6.3 Implementing the Proof : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 95 6.3.1 The Blocking Phase : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 96 6.3.2 The Propagation Phase : : : : : : : : : : : : : : : : : : : : : : : : : : : : 96 6.3.3 The Time Complexity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 99 6.4 Discussion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 7 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 104 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 106 Vita : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 112 ix Chapter 1 Introduction The theme of this thesis is geometric triangulations. These are face-to-face decompositions of domains or spaces into triangles in two dimensions or simplices in general dimensions. Computational work on geometric triangulations, or simply, triangulations, has been plentiful, ever since the beginning of the computer era. Many interesting theoretical properties have been discovered about triangulations, which in turn suggest the use of particular types of good or optimal ones. Unfortunately, many of these optimal triangulations have as yet no polynomial time construction methods and thus remain of limited significance in practice. Many computer programs written in the area are either for optimal triangulations of a small class or heuristics with no guarantee on the quality of the output triangulation. There remain numerous unsolved problems on constructing triangulations, all waiting anxiously for solutions. The pool of problems that was open a few years ago motivated our study, and this thesis reports on some solutions and encouraging results in two dimensions. In the rest of this chapter, we discuss two representative applications of triangulations (Section 1.1), introduce useful terminology (Section 1.2), survey open problems related to applications (Section 1.3), and preview material covered by subsequent chapters (Section 1.4). 1 1.1 Two Sample Application Areas Triangulating a geometric object or space is a popular decomposition method that has found many applications. In this section, we describe two major uses of triangulations; other applications will be mentioned where appropriate in later discussions. The main purpose here is to shed some light on the role of triangulations that will help us understand the relevance of the open problems discussed in Section 1.3. As such, we only highlight the typical steps involved in applications; specific details and other variations can be found in the references1. Finite Element Analysis. This is a discretization technique for solving partial differential equations. Many problems in engineering, including elasticity, electromagnetism, fluid dynamics, structural mechanics, biomechanics and many others, appear as variational forms where in each case a function is to be found that minimizes or maximizes a given set of equations. Very often, an exact solution is impossible and thus an approximation is necessary. Finite element analysis is one such approximation method [BaSu90, StFi73]. The analysis starts by creating a so-called mesh--possibly a triangulation--that decomposes the structure or the object of interest into small pieces called elements. Next, the partial differential equation is solved for each element with some lower order polynomial function. The solutions for the elements are then integrated into a solution for the problem. Then, some error indicator is obtained to decide whether any further computation is required to improve the current solution. The next iteration, if needed, will be performed with higher order polynomial functions or with improved mesh topology (via relocating the mesh vertices or refining elements into smaller ones), or combination of both. The mesh generation is indeed an important process. The overall quality of a computation depends on the types and shapes of the elements, and the number and distribution of the elements. One way to generate a mesh is to first spread vertices on the object, possibly taking distribution requirements into account, and then form non-overlapping elements using these vertices [Cave74]. Another way is to generate elements one at a time from the remaining object [GeSh90, Trac77]. Sometimes, the object is first decomposed into some manageable, for 1Because of the huge amount of literature in the area, the references quoted are by no means complete. 2 example, convex portions [Joe86, JoSi86] before a mesh is created. We refer to [HoLe88, Shep88] for surveys on mesh generation methods. Surface Interpolation. The objective is to construct a surface that passes through a given set of data points with corresponding data values. This process appears in a wide variety of scientific fields including mineral exploration, computer aided geometric design, medicine, digital terrain modeling and weather analysis. In these applications, the given points and values represent observed or computed values of some physical phenomena, and the interpolation schemes are used to construct surfaces that approximate other values, which may be difficult or impossible to obtain. Conditions, such as the continuity of partial derivatives (i.e., smoothness) of the surface, are usually assumed to limit the choice. A comprehensive list of references on the subject can be found in [FrSc87]. Let us consider the example of a given set of planar data points (xi; yi) with corresponding data values zi. The goal is to construct a bivariate function f (x; y) such that f (xi; yi) = zi, for all i. A typical three-step interpolation procedure to achieve this is as follows. First, construct a triangulation on the set of data points to divide the region of interest into triangles. Second, estimate partial derivatives of f with respect to x and y at each of the data points (xi; yi) using the data values of the data points connected to (xi; yi) in the triangulation. The plausible justification for taking the neighbors of (xi; yi) is that they tend to be close to (xi; yi) and should thus have an influence on this calculation. Third, interpolate the values of points within each triangle by some polynomial using the data values and the estimated partial derivatives at the vertices of the triangle. The surface f is then obtained by connecting the interpolated results on all the triangles, and some error bounds on the goodness of f can also be computed from the geometry of the triangles. 1.2 Terminology This section summarizes basic definitions and concepts needed throughout this thesis. The discussion is predominantly for the two-dimensional plane, R2, because results and problems of interest here are mostly two-dimensional. 3 Convexity. Denote by xy the edge, or line segment, that connects the points x; y 2 R2, and by jxyj the length of xy. The endpoints of xy are points x and y; they are, however, not considered as points on xy. For x; y; z 2 R2, xyz denotes the triangle with edges xy; yz and zx. A set C ` R2 is convex if for a; b 2 C, ab lies entirely in C; otherwise, C is non-convex. The convex hull of a set S, denoted by conv(S), is the smallest convex set in R2 that contains S. A region refers to the set of points in R2 bounded by a (simple) closed curve. The curve is also the boundary of the region. For example, a disk is a region bounded by a circle. We always refer to a region as a open set that does not contain points of its boundary, and use the closure of a region to mean the region plus its boundary. A convex region is a region whose set of points is convex. Plane Geometric Graphs. Let S be a finite set of n vertices, or points, in R2, and E a set of edges determined by S. We call G = (S; E) a plane geometric graph if (i) for every edge ab 2 E, ab " S = ;, and (ii) for every two edges ab 6= cd in E, ab " cd = ;. If E = ;, we refer to G simply as a (finite) vertex set, or point set, S. The connected components of R2 minus all vertices of S and all points on edges of E are the faces of G. Triangulations. A triangulation is a plane geometric graph T = (S; E) so that E is maximal. By maximality, edges in E bound conv(S) and divide its interior into disjoint faces bounded by triangles. These triangles are referred as triangles of T . We sometimes write T (S) to refer specifically to a triangulation T of S. As T is a connected plane graph, its jSj = n vertices, jEj = e edges, and f faces satisfy Euler's formula: n \Gamma e + f = 2; see, for example, [BoMu76]. In addition, if h is the number of edges in E bounding conv(S), then 3(f \Gamma 1) + h = 2e, by counting the edges in two ways. The left hand side counts 3 for each bounded face and h for the unbounded face; the right hand side counts 2 for each edge. We thus obtain e = 3n \Gamma h \Gamma 3 and f = 2n \Gamma h \Gamma 1. Because h is fixed for a fixed point set S, it follows that all triangulations of S have the same number of f \Gamma 1 triangles and e edges. 4 ffl ffl ffl fflfflffl ffl ffl S ffl ffl ffl fflfflffl ffl ffl G a b h cgf e d ffl ffl ffl fflfflffl ffl ffl a triangulation of S ffl ffl ffl fflfflffl ffl ffl a constrainedtriangulation of G ffl ffl ffl fflfflffl ffl ffl a Steinertriangulation of S ffl ffl ffl ffl fflfflffl ffl ffl a conformingtriangulation of G fflffl Figure 1.1: Examples on various types of triangulations for the point set S and the plane geometric graph G = (fa; b; c; d; e; f; g; hg; fbh; ce; cfg). A plane geometric graph G = (S; E) can be augmented with an edge set E0 until it is a triangulation T = (S; E [ E0), also referred to as a triangulation of G. If E 6= ;, we call T a constrained triangulation (of G), and E its set of constraining edges. Besides with edges, we can also augment G = (S; E) with a vertex set S0. A triangulation T obtained in this manner is called a Steiner triangulation (of G), and S0 the set of Steiner vertices. We call a Steiner triangulation with constraining edges a conforming triangulation. Refer to Figure 1.1 for an illustration. Unless stated otherwise, we talk about triangulations without Steiner vertices and without constraining edges. Polygons. A (simple) polygon is a plane geometric graph G = (S; E) where E and S form a single cycle. This cycle is the boundary of the polygon. It divides the plane into a bounded face, its interior, and an unbounded face, its exterior. We use polygon interchangeably to denote both the boundary (a curve) and its interior (a region or, more precisely, a polygonal region). A polygon is convex if its interior is convex, and it is called an n-gon if jSj = n. For example, triangles are convex 3-gons. We define quadrilaterals to be 4-gons, and pentagons to be 5-gons. Vertices of a polygon are always written in the order they appear on the boundary. Two vertices 5 are adjacent if they are incident to a common edge. A diagonal of a polygon is a line segment that connects two non-adjacent vertices and lies entirely in the interior. An ear of a polygon is a triangle bounded by two edges and one diagonal [Meis75]. Treating E as a constraining edge set, we can talk about constrained and Steiner triangulations for G. The restriction of one of these triangulations to the interior face of G is a polygon triangulation. Optimal Triangulations. A plane geometric graph G permits, in general, many possible triangulations. Various (shape) criteria can be used to classify some as optimal triangulations. Many of these criteria are defined as max-min (short for maximizes the minimum) or minmax 2 of some triangle or edge measure. The first quantifier is over all triangulations of G and the second is over all triangles or edges of a triangulation. Two examples of criteria are min-max angle and max-min angle. A criterion may or may not define a unique optimal triangulation. When Steiner vertices are allowed, we prefer optimal triangulations with small number of vertices, for obvious computational reasons. A max-min or a min-max criterion, in the case without Steiner vertices, can be extended naturally to its vector form. For example, consider the min-max angle criterion. For a triangulation A of G, we define its angle vector VA = (ff1; ff2; : : : ; fft), with ff1 * ff2 * : : : * fft the t largest angles of the t = f \Gamma 1 triangles of A. If B is another triangulation of G with angle vector VB = (fi1; fi2; : : :; fit), we say VB is (lexicographically) smaller than VA if there is an index 1 ^ j ^ t so that fii = ffi for 1 ^ i ! j and fij ! ffj. Then, the vector form of the criterion in this case defines a triangulation with the minimum angle vector. Similarly, the vector form of the max-min angle criterion defines a triangulation that lexicographically maximizes the non-decreasing vector of smallest angles of triangles. Additional optimal triangulations will be introduced in the next section. For now, we define the most prominent optimal triangulation of a point set S, named after the Russian mathematician Boris Delaunay. Delaunay Triangulations. An edge ab, for a; b 2 S, is a Delaunay edge if there is a circle through a and b so that all other points of S lie outside the circle. The collection of Delaunay 2Though min-min and max-max versions are possible, they are usually trivial and uninteresting. 6 edges defines a plane geometric graph D(S) known as the Delaunay triangulation of S [Dela34]. In the non-degenerate case, which excludes four or more points on a common circle, D(S) is indeed a triangulation. In fact, it is a triangulation that lexicographically maximizes the nondecreasing vector of smallest angles of triangles. In the degenerate cases, some faces of D(S) are convex polygons other than triangles, and these can further be subdivided into disjoint triangles using additional edges cd for c; d 2 S. The resulting triangulation is called a completion of D(S). In many situations, we make no distinction between Delaunay triangulations and their completions. Note that each edge cd of a completion satisfies the so-called empty disk property (with respect to S), i.e., there is a circle through c and d so that all other points of S lie outside the (open) disk bounded by the circle. For a general plane geometric graph G = (S; E) where E 6= ;, we extend the above definition to define constrained and conforming Delaunay triangulations. Two vertices a and b are visible from each other if the line segment ab does not intersect any constraining edges in E. A constrained Delaunay triangulation of G is a triangulation T = (S; E [ E0), where ab 2 E0 if a and b are visible from each other and ab satisfies the empty disk property with respect to only vertices visible from both a and b [LeLi86]. A conforming Delaunay triangulation of G is a completion of D(S [ S0) where each edge of G is the union of some edges and vertices of the completion [BFL88]. Time- and Storage-Complexity. The efficiency of an algorithm is measured by its timeand storage-complexity. Time refers to the number of steps, as a function of the input size n, needed to complete the computation. Storage refers to the amount of memory space needed and is also measured as a function of n. We assume the random access machine as our computational model and use the unit-cost measure which charges one unit of time per arithmetic operation [AHU74]. As a common practice, we talk about the asymptotic order or order of magnitude of a complexity function f (n) rather than the exact function itself. Thus, we write (i) f (n) 2 O(g(n)) if there is a positive constant c so that f (n) ^ c \Delta g(n) for all integers n exceeding some constant n0 * 0, (ii) f (n) 2 \Omega (g(n)) if g(n) 2 O(f (n)), and 7 (iii) f (n) 2 \Theta (g(n)) if f (n) 2 O(g(n)) and f (n) 2 \Omega (g(n)); see, for example, [PrSh85, page 8-10]. The terms linear, quadratic, cubic refer to polynomials in n with degree 1, 2, and 3 respectively. A polynomial time algorithm is an algorithm whose time-complexity is some polynomial in the input size n. For practical purposes, efficient algorithms commonly refer to those with low order polynomial time such as linear, O(n log n), and quadratic. A computational problem is said to be in the class P if it has a polynomial time algorithm, specifically, deterministic polynomial time algorithm. Besides P, the class NP is of interest here. A problem is in NP if it has a polynomial time, non-deterministic algorithm (see [GaJo79] for detailed discussion). P is in NP but the converse relation is not known. There are decision problems in NP known to be equivalent, by a polynomial time transformation, to all other problems in NP. Such problems are termed NP-complete problems, and are unlikely to be in P. Data Structures. Data structures are ways to organize data in a computer. Common examples of data structures are arrays, stacks, priority queues, and trees. These are wellknown and discussed in many standard texts on algorithms; see, for example, [CLR90]. We next introduce the quad-edge data structure [GuSt85] to store a plane geometric graph G. Loosely speaking, it stores each edge of G four times, twice for its two incident faces and twice for its two endpoints3. Figure 1.2 shows an example of the quad-edge structure for a plane geometric graph that bounds polygonal regions A and B. Strictly speaking, A is not a polygonal region in the usual sense of the term since A contains a "crack" due to edges f g and gh. The quad-edge representation treats A as a single region bounded by those (oriented) edges for which it lies to their left. As such, we need not distinguish a region with cracks from a genuine one as long as its interior remain simply connected. By this we mean that different (simple) paths (disjoint from the edges) between two points in the interior can be continuously deformed into each other. 3Often, we do not need all the four (oriented) versions of an edge, but rather only the two versions that correspond to the endpoints of the edge. 8 1 2 3 4 5 6 7 8 9 4 5 7 8 6 9 3 2 1A c B BA d e f g h a b f a b cd e g h Figure 1.2: To the right is a schematic diagram of a quad-edge representation of the plane geometric graph to the left. Quad-edge records are shown represented by crosses which are linked by solid and dotted curves. 1.3 Survey of Problems In the following subsections, we describe questions about constructing optimal triangulations. Some of these questions are answered in this thesis, and some remain open. Our emphasis is on efficiency, that is, algorithms that run in low order polynomial time. As a fixed set of n vertices generally has exponentially many triangulations (an upper bound of 1013n on the number of triangulations of a set of n points in R2 is known [ACNS82]), it is not feasible to exhaustively search the set of all triangulations for an optimal one. Also, many straightforward ideas usually do not work as we will see in later chapters. The same can be said about Steiner triangulation problems. Most existing techniques for constructing optimal triangulations are surveyed in Chapter 2. Sections 1.3.1 to 1.3.4 collect problems on non-Steiner triangulations, and Section 1.3.5 on Steiner triangulations. We note that some non-Steiner cases can be extended naturally to constrained or Steiner cases. Also, max-min or min-max criteria mentioned in these problems can be substituted by their corresponding vector forms. As mentioned, all problems are stated as questions on the existence of efficient algorithms, particularly, sequential ones. The same questions can also be asked in relation to other computational issues, such as parallel computation, dynamic inputs, etc. These questions will not be discussed. 9 1.3.1 Angle Criteria For many applications, a "good" triangulation is one without thin or elongated triangles. Put it differently, triangles that differ as little as possible from equilateral triangles are usually preferred. One way to capture this notion is to impose angle criteria such as min-max angle or max-min angle. This indeed agrees with the fact that angle is an important quantity in bounding the errors of computations in finite element analysis and surface interpolation. In particular, there are bounds that relate the error directly to the size of smallest angles, and others that relate it to the size of the largest angle; see, for example, [Akim84, BaAz76]. Delaunay triangulations optimize the max-min angle criterion, and can be computed in \Theta (n log n) time by a number of algorithms (Section 2.4). On the other hand, the construction problem for min-max angle criterion was open for some time [Hans90]. An efficient solution to the problem is provided in Section 4.1. Problem 1 How fast can we compute a min-max angle triangulation of a point set? Besides min-max and max-min angle conditions, a limit on the range of the angle values is another natural condition. We note that this, however, may not always be achievable without introducing Steiner vertices. For example, it is not always possible to use only acute angles. The next question is a variant of this general issue, and is still open at this day. Problem 2 Given a point set S, how fast can we compute a triangulation of S that minimizes the number of obtuse angles? 1.3.2 Length Criteria For finite element analysis, edge lengths are sometimes part of error bounds. Specifically, the sharpness of some error bounds is inversely proportional to the longest side of a triangle [BrZl70, WGS90]. For surface interpolation, we sometimes use vertices of a triangle as "nearby" locations to estimate the data values of points in its interior. It is thus desirable to have interior points of the triangle as close to its vertices as possible [Akim84, page 44]. Also, this may help in estimating partial derivatives of other vertices connected to the triangle. Both applications 10 suggest the criterion of min-max length. Of course, this is ignoring the tradeoff and interplay between angle and length criteria; they may not be optimized simultaneously. We can still formulate the problem on min-max length criterion (which also appears in [PeKe87, page 175], [Schu87, page 221], and [WaPh84, page 218]), and provide a solution in Chapter 5. Problem 3 How fast can we compute a min-max length triangulation of a point set? The following problems on length criteria are still open. Problem 4 is the "reverse" of the previous problem, and Problem 5 is notoriously difficult [Lloy77, PlHo87] (see Section 2.5 for some general discussion). Problem 4 How fast can we compute a max-min length triangulation of a point set? Problem 5 Given a point set S, how fast can we compute a triangulation of S that minimizes the sum of edge lengths? 1.3.3 Other Reasonable Criteria As mentioned, error bounds are sometimes expressed in terms of angles as well as edge lengths. We can thus consider to optimize measures that relate, in some ways, to both. These include, for instance, the area of a triangle and the aspect ratio. The latter is the ratio of the longest edge to the altitude from this edge. The degree of a vertex is yet another interesting measure as it signifies the importance of the vertex in computations [FrFi91]. It is, however, an NPcomplete problem to decide whether a point set with constraining edges has a triangulation with vertex degree at most 7 [Jans92]. No solution is known for the next problem compiled from [Schu87, page 222], [Barn77, page 84], [GeSh90, page 202], and [GCR77, Lind83]. Problem 6 Can a min-max or a max-min optimal triangulation based on any one of the following quality measures be computed efficiently: area; aspect ratio; degree; radius of inscribed circle; ratio of the area of the inscribed circle to the area of the triangle; ratio of the diameter of the inscribed circle to the radius of the circumscribed circle? 11 Two other measures are intentionally left out from the above; these are the max-min height [GCR77] and the min-max eccentricity [GCR77, WaPh84]. Height of a triangle refers to the length of the altitude from its longest side, and eccentricity of a triangle refers to the infimum over all distances between the center of its circumscribed circle to points in the closure of the triangle. These are formulated separately as they now have efficient solutions discussed in Sections 4.2 and 4.4. Problem 7 How fast can we compute a max-min height triangulation of a point set? Problem 8 How fast can we compute a min-max eccentricity triangulation of a point set? 1.3.4 Data Dependent Criteria Notice that all the above mentioned optimal triangulations for use in interpolating z = f (x; y) do not take the data values into account. This may not be desirable since some shape information "encoded" in the data values has great influence on the quality of the interpolation. Indeed, a study shows that the best triangulation should have triangles with long edges in the direction of minimum curvature and short edges in the direction of maximum curvature, rather than simply having triangles close to equilateral ones [Nadl85]. This requirement is an example of a data dependent criterion. In general, a data dependent criteria is one that takes into account more than just the locations of the vertices. Work done on data dependent criteria can be found in [DLR90b, QuSc90, Ripp92, RiSc90]. We sample only two such criteria for interpolating z = f (x; y). They are the min-max AABNV, short for acute angle between normal vectors [DLR90a, DLR90b], and the min-max slope [WaPh84, page 218]. To understand these, we imagine that a triangulation on points (xi; yi) in the plane is actually a "spatial triangulation" on (xi; yi; zi) in space, i.e., a terrain formed by triangular faces. The intrinsic dimension of this triangulation is two and it lives in R3. It should be clear that we can talk about normal vectors and slope of these faces with respect to the plane z = 0. This naturally defines the mentioned criteria. The plausible justification for these criteria is that they model gradual change in the z values, in particular z values across faces, and thus better control the smoothness condition across faces in the interpolation. 12 Problem 9 Can an optimal triangulation defined by any one of the following criteria be computed efficiently: min-max AABNV, minimum sum of AABNV, and minimum sum of the squares of AABNV? Problem 10 How fast can we compute a min-max slope triangulation of a point set? Problem 9 is still open; heuristic algorithms are used in practice [DLR90a]. On the other hand, there is an efficient algorithm for problem 10 in Section 4.3. 1.3.5 On Steiner Triangulations Many open problems on Steiner triangulations are summarized in [BeEp92]; we will highlight only two here. We note that constraining edges are commonly used to model important features of objects or spaces to be triangulated, and they constitute part of the edges in the resulting triangulation. Popular optimal triangulations with constraining edges include the constrained and conforming Delaunay triangulation. There are already efficient construction algorithms for the former [Chew89, Seid88], but not for the latter [NaSr91]. Problem 11 How fast can we compute a conforming Delaunay triangulation for a plane geometric graph? Chapter 6 contains a polynomial time solution to the problem. The next open problem is related [BeEp91], since a triangulation without obtuse triangles is indeed Delaunay. Problem 12 How fast can we compute a conforming triangulation without obtuse triangles for a plane geometric graph? 1.4 Overview of the Thesis The following chapters discuss algorithms on computing optimal triangulations. Chapter 2 surveys some prior work relevant to our subsequent discussions in Chapters 3 through 6. 13 Chapter 3 discusses a new algorithmic technique, called the edge-insertion paradigm, which computes optimal triangulations for plane geometric graphs. We present an abstract view of the paradigm and state two conditions for criteria that can be optimized. Four examples of criteria known to satisfy these conditions are the min-max angle, max-min height, min-max slope and min-max eccentricity; these are discussed in Chapter 4. The material of these two chapters also appears in [ETW90, BEEMT92]. Chapter 5 presents a quadratic time solution to the min-max length triangulation problem of a point set. The result is applicable to edge lengths measured by an arbitrary normed metric, including the Euclidean distance and the more general lp metrics. It is currently the only (nontrivial) length criterion that can be computed efficiently. Our solution also provides additional insight into optimal triangulations under edge length criteria. This chapter also appears in [EdTa91]. Chapter 6 considers conforming Delaunay triangulations. We show that, for every plane geometric graph G with n vertices and m edges, there is a conforming Delaunay triangulation for G with 4m2n + 10mn + 4n vertices. The result also implies an efficient algorithm to compute these vertices and thus a conforming Delaunay triangulation. This is also published in [EdTa92]. We note that all solutions found in the above chapters are reasonably simple and not exceedingly difficult to implement. They are currently the only solutions of their kinds that run in polynomial time. The data structures needed are mainly arrays, stacks, priority queues, trees, and quad-edges. For each algorithm the tricky part is its correctness, which is based on subtle observations and has a relatively involved and lengthy proof. Chapter 7 summarizes our work and notes some difficulties of three-dimensional problems. 14 Chapter 2 Some Prior Work This chapter reviews some computational work on triangulations. Materials covered are relevant to discussions in subsequent chapters. Further information on work done in the area can be found in the survey papers [Aure91, BeEp92] and the two books on computational geometry [Edel87, PrSh85]. A quick reference to this chapter is as follows. 1. The plane-sweep method computes an arbitrary triangulation for a plane geometric graph of n vertices in \Theta (n log n) time and linear storage (Section 2.1). 2. Dynamic programming is a general method to compute optimal polygon triangulations in polynomial time (Section 2.2). 3. The edge-flip scheme computes the Delaunay triangulation in quadratic time and linear storage. With some modifications, it serves as a popular heuristic for computing other optimal triangulations (Section 2.3). 4. mst(S) ` rng(S) ` gg(S) ` D(S), where S is a point set, mst(S) its minimum spanning tree, rng(S) its relative neighborhood graph, gg(S) its Gabriel graph, and D(S) its Delaunay triangulation (Section 2.4). 5. There is a subgraph approach to compute a triangulation of a point set so that its total edge length is a factor of O(log n) higher than that for the minimum length triangulation of the point set (Section 2.5). 15 2.1 Plane-Sweep Plane-sweep is a simple way to construct an arbitrary triangulation for a plane geometric graph. Let us first see how to apply plane-sweep to a set of vertices p0; p1; : : : pn\Gamma 1, sorted in this order from left to right. We conceptually sweep a vertical line from left to right, and maintain a triangulation for the vertices already encountered. When we reach vertex pi, we add the edge pipi\Gamma 1. Then we march in a counterclockwise and then a clockwise direction along the convex hull of p0; p1; : : : ; pi\Gamma 1 to add edges between pi and convex hull vertices. To perform this for the counterclockwise direction, we first set pj := pi\Gamma 1 and let pk be the convex hull vertex following pj in this direction. If pi; pj and pk form a right turn1, we add pipk, set pj := pk and repeat the test; otherwise, we are done for pi. The clockwise direction is done symmetrically. The time spent to add an edge is constant since marching along convex hull edges in a quad-edge data structure takes constant time per step. Thus, a total of O(n) time is needed to create O(n) edges for the output. Sorting the n vertices (with x-coordinate as the primary key and y-coordinate as the secondary key) takes \Omega (n log n) time, which implies that plane-sweep takes time O(n log n) to compute an arbitrary triangulation for an unsorted set of n vertices. Although plane-sweep is a rather simple-minded technique, it constructs a triangulation in asymptotically optimal time. Indeed, \Omega (n log n) is necessary because triangulation is no easier than sorting [PrSh85, page 188]. Plane-sweep works equally well in time O(n log n) to construct a constrained triangulation for a plane geometric graph. In this case, we need a dictionary, for example, a splay tree, to record "active" (constraining line) segments intersecting the sweep line in sorted order. We also record the rightmost vertex within the region between two adjacent active segments (and above the topmost and below the bottommost active segment). The triangulation is constructed incrementally to the left of the sweep line. Each rightmost vertex recorded plays the role of pi\Gamma 1 in the vertex set case. The extra effort not encountered for the vertex set case is O(log n) for 1Three vertices pi = (ssi 1; ssi2); pj = (ssj1; ssj2) and pk = (ssk1; ssk2) form a right turn when vertex pk is on the right of the directed line ~pipj. This is the case when the determinant fififi fifi ssi1 ssi2 1 ssj1 ssj2 1 ssk1 ssk2 1 fififi fifi ! 0: 16 each insertion, deletion, and search in the dictionary. The total effort is O(n log n), the same as before. 2.2 Dynamic Programming Dynamic programming finds the optimal solution by systematically combining solutions of smaller problems. Let us see how the method computes a minimum length polygon triangulation, i.e., a polygon triangulation that minimizes the sum of edge lengths. Let P be the simple polygon with vertices p0; p1; : : : ; pn\Gamma 1. Let L[i; i + j] be the total edge length of an optimal triangulation for the region P 0 bounded by pi+j pi and the edges from pipi+1 through pi+j\Gamma 1pi+j , where indices are modulo n. We compute L[i; i + j] recursively as follows. Clearly, pi+j pi is the only edge of P 0 possibly not in P . If pi+j pi crosses the boundary of P , then P 0 is not a simple polygon and we thus set L[i; i + j] := 1. Otherwise, pi+jpi is either an edge or a diagonal of P . In either case, pi+jpi is a side of some triangle in the optimal triangulation of P 0. Such a triangle decomposes P 0 into two smaller (possibly empty) subpolygons of P 0, which must also be optimal in terms of total edge length; we, thus, have L[i; i + j] := jpi+jpij + mink=1;2;:::;j\Gamma 1(L[i; i + k] + L[i + k; i + j]): With the above, we can find L[0; n \Gamma 1] by three nested loops, varying j from 1 to n \Gamma 1, i from 0 to n \Gamma 1, and k from 1 to j \Gamma 1, to first solve small problems and then combine their solutions to solve larger problems. The loop with k also checks whether pi+jpi crosses the boundary of P by testing whether any edge pi+kpi+k+1 crosses2 pi+jpi. To obtain the optimal triangulation for P , we record the k that is chosen to optimize each L[i; i + j], and use it later to trace the triangulation. In total, the algorithm takes cubic time for the nested loops, and quadratic storage for keeping L[i; j] and k [Gilb79, Klin80]. It is easy to see that the algorithm can be modified to compute other criteria. For example, we can compute a min-max angle triangulation for a simple polygon in the same amount of time and storage. Also, we can compute a triangulation that lexicographically minimizes the non2Two edges ac and bd cross iff abcd is a convex polygon, i.e., abc, bcd, cda and dab are all left turns or all right turns. 17 increasing vector of largest angles of triangles, but the time- and storage-complexity in this case are a factor of n higher as we need to compare and store vectors of linear size. Incidentally, the dynamic programming approach is not necessarily the most efficient way to compute optimal triangulations; for instance, the min-max angle criterion can actually be computed in O(n2 log n) time and linear storage (Section 4.1). 2.3 Edge-Flip Edge-flip is a local optimization method that operates on two triangles whose union forms a convex polygon. It was used in [Laws72] to remove small angles: the edge bd shared by triangles abd and cbd is replaced or flipped when the smallest angle in these triangles is smaller than that of acb and acd. In effect, an edge-flip replaces two existing triangles by two new ones. This operation was incorporated into a plane-sweep scheme (Section 2.1) to incrementally compute a locally optimal triangulation T (S) [Laws77], that is, one that has no edge-flip to improve its quality. It was found that this locally optimality actually implies that T (S) is a completion of D(S) [Dela34, Sibs78]. Since any two completions of D(S) have the same value for their smallest angles, T (S) is actually a max-min angle triangulation (see [Edel87, page 301-303]). There are various possibilities to implement the above scheme. One variant is to first compute an arbitrary triangulation, T (S), and then use a stack to schedule edge-flips. First, all edges of T (S) are pushed onto the stack. Then, edges are popped one by one to check for possible edge-flips. When an edge-flip bd occurs, each of the other four edges of the two triangles incident to bd is pushed onto the stack if it is not already there. The algorithm stops when the stack is empty, which occurs after at most O(n2) edge-flips where n = jSj; see, for example, [Edel92]. Many applications adapt the edge-flip method to optimize other criteria, by changing the condition for edge-flip. These, however, do not always compute the defined optimal triangulations and are thus heuristic schemes; see, for example, [DLR90a]. Also, it is unclear how long each heuristic runs since edges removed can be recycled back for further edge-flips. One possible way to cope with this difficulty is to impose a time limit on the algorithm; one other is to use a priority queue (instead of a stack) to schedule edge-flips and stop the algorithm once 18 an unsuccessful edge-flip is encountered. When this latter heuristic is applied to the minimum length criterion (for which we flip long edges for short ones), it guarantees that at most O(n2) edges are flipped as removed edges do not reappear. 2.4 Delaunay Triangulations and Related Structures The Delaunay triangulation has been a prominent subject in the study of triangulations; it is related to many positive results known in the area. Besides the O(n2) time edge-flip method (Section 2.3), Delaunay triangulation can be computed in \Theta (n log n) time by diverse algorithmic paradigms such as divide-and-conquer [GuSt85, ShHo75], geometric transformation [Brow79], and plane-sweep [Fort87]. Furthermore, it can be computed in time O(n log n) with high probability by randomized incrementation [GKS92]. Among all triangulations of a given point set S, the Delaunay triangulation optimizes criteria such as the max-min angle [Sibs78], the min-max circumscribed circle [D'AS89], the min-max smallest enclosing circle [D'AS89, Raja91], and the minimum integral of the gradient squared [Ripp90]. As a graph structure, the Delaunay triangulation of S, D(S), is the straight line dual of the so-called Voronoi diagram [Voro07, Voro08, Aure91]. Various subgraphs of D(S) have been studied in the literature. Three of those subgraphs, satisfying mst(S) ` rng(S) ` gg(S) ` D(S) will now be discussed. The Gabriel Graph of S, gg(S). Given a vertex set S, gg(S) is a unique graph that contains an edge pq, p; q 2 S, if all points in S \Gamma fp; qg are outside the closure of the disk with diameter pq. It is defined by Gabriel and Sokal [GaSo69] for use in geographical analysis, and, more generally, for clustering points. Obviously, an edge in gg(S) is also a Delaunay edge, but the converse is not necessarily true; thus, gg(S) ` D(S). The Relative Neighborhood Graph of S, rng(S). An edge pq belongs to rng(S) if jpqj ^ min x2S\Gamma fp;qg maxfjxpj; jxqjg: 19 This definition goes back to Toussaint [Tous80], who modified a similar definition by Lankford [Lank69], for use in pattern recognition. Equivalently, the lune of pq, denoted by *pq, is the set fx 2 R2 : maxfjxpj; jxqjg ! jpqjg, and pq in rng(S) if *pq " S = ;. It is obvious that *pq [ fp; qg contains the closure of the disk with diameter pq; thus, each edge of rng(S) is also an edge of gg(S). Therefore, rng(S) ` gg(S). A Minimum Spanning Tree of S, mst(S). It is a spanning tree, i.e., a connected and cycle free graph, on S with the minimum total edge length. From the definition, the lune of each edge pq in mst(S) must be empty. Otherwise, there is a point r 2 *pq so that pr and qr are not both in mst(S), as mst(S) is cycle free. The spanning tree obtained by replacing pq with either pr or qr has smaller total edge length than mst(S), a contradiction. Thus, we have mst(S) ` rng(S). All the graphs, mst(S); rng(S); gg(S); and D(S) are connected since mst(S) is connected, and are plane since D(S) is plane. An efficient way to compute mst(S), rng(S) or gg(S) is to first compute D(S) with some of the methods mentioned above, and then remove invalid edges; see, for example, [MaSo80, Supo83, Yao82]. 2.5 Minimum Length Triangulations We have seen in Section 2.2 the cubic time (dynamic programming) algorithm for constructing minimum length triangulation for a simple polygon. The same problem for a point set is open (Section 1.3.2, Problem 5) [Lloy77]. We mention in the following an interesting attempt, termed subgraph approach, for finding a polynomial time solution to the problem. The idea is to convert a point set problem to a number of (simple) polygon problems, which can then be solved in polynomial time, for example, by dynamic programming. This conversion is done by adding sufficiently many non-intersecting edges to the point set so as to divide its convex hull into a number of polygons. For this to work, we must assert that these additional edges are indeed part of an optimum and are computable in polynomial time. Unfortunately, such a set of edges has not been found. Currently, only a small subset of edges can be identified (see [Gilb79] for details). 20 Despite the above difficulty, the subgraph approach was used as a powerful technique by Lingas [Ling87] and Plaisted and Hong [PlHo87, OTZ88] to compute a triangulation with a guaranteed bound on its total edge length. The former uses the union of the convex hull and a spanning forest to reduce a given point set problem to several polygon problems. Under the assumption of a uniform point distribution, the result is a triangulation with total edge length within a factor of O(log n) from the optimum with high probability, and the expected length of the solution is of the same order as that of the optimum. The latter generates polygon problems by computing the convex hull and a star graph from each point to its nearby neighbors. After optimally triangulating all polygons, this method generates a solution with total edge length within a factor of O(log n) from the optimum. 21 Chapter 3 The Edge Insertion Paradigm This chapter introduces an operation called the edge-insertion to locally improve a triangulation. Basically, the operation adds a new edge to the triangulation to be improved, deletes old edges intersecting the new edge, and retriangulates the resulting polygons supported by the new edge. This is in some sense a generalization of the edge-flip operation (Section 2.3)--an edge-insertion generally intersects many old edges, but is the same as an edge-flip when it intersects only one. Its ability to intersect many edges turns out to be very powerful; its formalism into an iterative improvement scheme, termed the edge-insertion paradigm, computes a few min-max and max-min optimal triangulations for which edge-flip paradigm fails, as shown in the next chapter. In the following, we examine an abstraction of the edge-insertion paradigm based on two sufficient conditions for the min-max (and max-min) criteria that it can optimize. Section 3.1 formalizes the basic version of the paradigm, and Section 3.2 states the two sufficient conditions. Then, Section 3.3 proves the correctness of the paradigm when applied to such criteria. Section 3.4 discusses refinements to the paradigm, Section 3.5 presents some extensions, and Section 3.6 summarizes this chapter. 22 3.1 The Paradigm Let S be a point set in R2, and let x; y; z be points in S. Recall that xy denotes the line segment that connects x and y, and xyz denotes the triangle with vertices x; y; and z. We call xyz an empty triangle if all other points of S lie outside the closure of xyz. A measure _ is a function that maps each triangle xyz to a real value _(xyz). Examples of measures that are of particular interest here are largest angle, height, slope, and eccentricity of a triangle. We restrict our attention to min-max criteria, that is, for each _ we consider the construction of a triangulation of S whose maximum _(xyz) over all its triangles is the smallest among all possible triangulations of S. Max-min criteria can be simulated by considering \Gamma _. The measure of a triangulation A is defined as _(A) = maxf_(xyz) : xyz a triangle of Ag. If A and B are two triangulations of a common point set, then B is called an improvement of A, denoted by B OE A, if _(B) ! _(A), or _(B) = _(A) and the set of triangles xyz in B with _(xyz) = _(B) is a proper subset of the set of such triangles in A. A triangulation A is optimal for _ if there is no improvement of A. The formal specification of the edge-insertion of qs, q; s 2 S, into a triangulation A of S is as follows. Function Edge-insertion(A, qs): triangulation. 1. B := A. 2. Add qs to B and remove from B all edges that intersect qs. 3. Retriangulate polygons P and R constructed in step 2. 4. return B. q s P R fflffl fflffl fflffl ffl fflffl ffl ffl ffl ffl Figure 3.1: P and R are created by the removal of edges intersecting qs. In step 2, P and R created are not necessarily simple polygons in the usual meaning of the term, as shown by Figure 3.1. Although their interiors are always simply connected, there can 23 be edges (or "cracks") contained in the interiors of their closures. Nevertheless, as discussed in Section 1.2, each such edge can be treated as if it consisted of two edges, one for each side, which then allows us to treat P and R as if they were simple polygons. As such, we can triangulate P and R in step 3 in an optimal fashion (minimizing the maximum _) by, for example, dynamic programming (Section 2.2). With the edge-insertion operation, we formulate the most basic version of the edge-insertion paradigm as follows; it tries all possible edge-insertions and halts when no edge-insertion improves the current triangulation. Input. A set S of n points in R2. Output. An optimal triangulation T of S. Algorithm. Construct an arbitrary triangulation A of S; repeat T := A; for all pairs q; s 2 S doB := Edge-insertion(A; qs); if B OE A then A := B; exit the for-loop endif endfor until T = A. To compute an optimal triangulation, this paradigm assumes that there is an edge-insertion that improves A whenever A is not yet optimal. Section 3.2 presents two conditions on measures for which the assumption is true, and Section 3.3 proves this assertion. Assuming this, we argue that the above algorithm runs in time O(n8). A single edge-insertion operation takes time O(n3) when retriangulating by dynamic programming, as long as the measures of any two triangles can be compared in constant time. Thus, the for-loop takes time O(n5) per iteration of the repeat-loop. Finally, the repeat-loop is iterated at most O(n3) times because there are only \Gamma n3\Delta triangles spanned by S, and each iteration permanently discards at least one of them when it finds an improvement of the current triangulation. 24 3.2 Two Sufficient Conditions Again, let S be a set of n points in R2. For each triangle xyz, x; y; z 2 S, we designate one or more vertices as anchors of xyz, depending solely on the measure _. For all but one of the measures of interest in the next chapter, vertices with the largest angle are anchors. In these cases, each non-isosceles triangle has a unique anchor. Let T be a triangulation of S, and let xyz be an empty triangle of S. We say that T breaks xyz at y if it contains an edge yt with yt " xz 6= ;. Note that if T breaks xyz at y, then it can neither break it at x nor at z since T is a plane graph. We are now ready to formulate two conditions for measures _. They both suffice to show that the edge-insertion paradigm computes a global optimum (i.e., min-max _). The first condition requires that every improvement of a triangulation A of S has an edge that breaks one worst triangle of A at its (unique) anchor. Precisely, we require that for every triangle xyz of A, if T neither contains xyz nor breaks it at its anchor(s), then maxf_(A); _(T )g ? _(xyz). (I) The second condition is a stronger version of (I). It further requires that _(T ) is no better than measures of those triangles in A which T does not break at their anchors. Specifically, we require that for every triangle xyz of A, if T neither contains xyz nor breaks it at its anchor(s), then _(T ) ? _(xyz). (II) We will see in Sections 4.3 and 4.4 that the slope and the eccentricity satisfy (I) but not (II). This shows that (I) is strictly weaker than (II). Because of the greater generality of (I), we can only derive an O(n3) time refinement to the edge-insertion paradigm, as compared to O(n2 log n) time refinement for (II). 25 3.3 The Cake Cutting Lemma This section shows that if A is not yet optimal for measure _ satisfying condition (I), then there is an edge whose insertion leads to an improvement, specifically an edge breaking a worst triangle at its anchor. This is achieved through the following two lemmas. The argument uses only (I), so also applies when (II) is satisfied. Cake-Cutting Lemma. Assume _ satisfies condition (I). Let T OE A be two triangulations of a point set S; let pqr be a triangle in A but not in T with _(pqr) = _(A); let q be an anchor of pqr; and let qs be an edge in T that intersects pr. Let P and R be the polygons generated by adding qs to A and removing all edges that intersect qs. Then there are triangulations P and R of P and R with _(pqr) ? _(P) and _(pqr) ? _(R). Proof. We focus on triangulating P ; R is triangulated similarly. Imagine we have P and T on separate pieces of transparent paper that we lay on top of each other so that the vertices of P match those corresponding ones in T . Next, we clip everything of T outside P . Now, we see generally many edges of T cutting through P , but none of them can meet qs as qs 2 T . Let us call each connected component of an edge intersected with the interior of P a clipped edge. Since P is not necessarily convex, several clipped edges can belong to the same edge of T . Our plan is to use these clipped edges as guides to successively remove ears from P to obtain a required P. If no clipped edge exists, then P has only three vertices and therefore must be a triangle of T . Because this triangle is not in A and T OE A, the triangle has measure less than _(A). So we are done. In the following, we thus assume the existence of at least one clipped edge. Denote by q = p0; p1; : : : ; pk; pk+1 = s the sequence of vertices of P . Claim 1. For 1 ^ j ^ k, if "pj\Gamma 1pjpj+1 ! ss, then pj\Gamma 1pj+1 is a diagonal of P . Proof (of Claim 1). By construction of P , it is possible to find non-intersecting line segments pj\Gamma 1x and pj+1y, both inside P , so that x and y lie on qs. (If j = 1, then x = pj\Gamma 1 = q; if j = k, then y = pj+1 = s.) The (possibly degenerate) pentagon xpj\Gamma 1pjpj+1y is part of P , and because the interior angles at pj , x, and y measure less than ss, edge pj\Gamma 1pj+1 is a diagonal of the pentagon and therefore also of P . This completes the proof of Claim 1. 26 A clipped edge divides P into two polygons, the near side supported by qs and the far side not supported by qs. Claim 2. There is at least one clipped edge whose far side is a triangle. Proof (of Claim 2). Let xy be a clipped edge so that its far side, F , contains no further clipped edge. Let ab be the edge in T that contains xy, and let abc be the triangle in T that lies on the same side of the line through xy as F . We have F ` abc for otherwise F contains a clipped edge belonging to ac or bc. Also, all vertices of F , except possibly x and y, are points in S and therefore equal to a, b, or c. Thus, F is a required triangle. This proves Claim 2. The clipped edges xy that satisfy Claim 2 fall into four classes as illustrated in Figure 3.2. An ear pi\Gamma 1pipi+1 so that xy is a clipped edge with far side xpiy can now be removed from q s pi\Gamma 1 pi pi+1 ffl ffl fflffl ffl ffl ffl fflffl ffl ffl ffl fflffl ffl ffl ffl fflffl ffl Figure 3.2: A clipped edge xy that satisfies Claim 2 has zero, one, or two endpoints on edges of P . P , leaving a polygon P 0 with one less vertex. Claims 1 and 2 remain true for P 0 because the removed ear is not supported by qs. So we can iterate and compute a triangulation P of P . Symmetrically, we get a triangulation R of R. Let B be the thus obtained triangulation of S. Claim 3. _(pqr) ? _(abc) for all triangles abc in P and R. Proof (of Claim 3). It suffices to show the claim for triangle abc in P and R with maximum _. Assume without loss of generality that abc is in P and _(abc) = _(B). At the time immediately before abc was removed by adding ac, there was a clipped edge xy with far side xby. Hence, T does not break abc at b, and by construction, A breaks abc at b and therefore neither at a nor at c. 27 If xy = ac, then abc is a triangle in T but not in A, and therefore _(pqr) ? _(abc). So, assume xy 6= ac. Then, if b is an anchor of abc, (I) implies that maxf_(B); _(T )g ? _(abc) as T does not break abc at b nor does it contain abc. This simply means that _(T ) ? _(abc) because _(B) 6? _(abc), and therefore _(pqr) ? _(abc). Otherwise, a or c is an anchor. As in the previous case only with T replaced by A, we obtain maxf_(B); _(A)g ? _(abc) from (I) and thus _(pqr) = _(A) ? _(abc). This completes the proof of Claim 3 and also the Cake-Cutting Lemma. The Cake-Cutting Lemma now shows that the basic edge-insertion paradigm cannot get stuck in a local optimum for _ satisfying condition (I). Lemma 3.1 Assume _ satisfies condition (I). Let A be a non-optimal triangulation of a point set S. Then there is an edge-insertion operation that improves A. Proof. Let B be an improvement of A and consider a triangle pqr in A with _(pqr) = _(A) that is not in B. Assuming q is an anchor of pqr, condition (I) implies that B contains an edge qs with qs"pr 6= ;. Let P and R be the polygons generated by adding qs and deleting the edges that intersect qs. The Cake-Cutting Lamma implies that there are polygon triangulations P and R of P and R with _(P) and _(R) both smaller than _(pqr). 3.4 Refinements of the Paradigm We now refine the basic paradigm for measures satisfying (I) and (II). Both refinements are specializations of the algorithm given below. It differs from the basic paradigm in two major ways. First, edge-insertions are restricted to candidate edges qs that break a worst triangle pqr at its anchor q. These edges are tried in a sequence, say qs1; qs2; : : :, etc. Second, the two polygons created by adding qs are retriangulated by repeatedly removing ears (as in the proof of the Cake-Cutting Lemma), rather than by dynamic programming. We use the notation si+1 = next(si). 28 Input. A set S of n points in R2. Output. An optimal triangulation T of S. Algorithm. Construct an arbitrary triangulation A of S; repeat T := A; find a worst triangle pqr in A, let q be its anchor, and set s := s1; while s is defined doB := A, add qs to B, and remove all edges that intersect qs; (partially) triangulate the two polygons P and R by cutting off ears xyz with _(xyz) ! _(pqr); if P and R are completely triangulated thenA := B; exit the while-loop else s := next(s) endif endwhile until T = A. Two remarks are in order. First, this algorithm finds a triangulation with min-max triangle measure, but not necessarily an optimal triangulation in the sense that the set of worst triangles is minimal. To achieve this slightly more ambitious goal, the repeat-loop must not halt until all worst triangles have subjected to unsuccessful edge-insertions. This requires only minor modification to the algorithm. Second, in an implementation of the algorithm we would not really copy an entire triangulation. Instead of the assignment T := A, we would use a flag to check whether an iteration of the repeat-loop produced an improvement. And, the assignment of B := A and the subsequent A := B can be avoided by making changes directly in A and undoing them to the extent necessary. The following subsections explain some of the steps in greater details and analyze the timeand storage-complexity of the two refinements. 3.4.1 Triangulating by Ear Cutting -- Part 1 As implied by the proof of the Cake-Cutting Lemma, the sequence in which ears are removed from P is immaterial so long as only the last is supported by qs. Additionally, three consecutive vertices is an ear of the remaining portion of P yet to be triangulated if they form an angle 29 less than ss inside P . This condition is equivalent to they form a left turn when vertices of P are listed in a counterclockwise order. Thus, the triangulation of P can be implemented using a stack and with simple test of an ear, so that it runs in time linear in the size of P . Here are the details. We first initialize the stack, say stackP, by pushing q followed by p. After that, we consider the other vertices of P one by one in order. Each time a vertex pi is considered, we first reset the stop indicator, repeat the cutearP(pi) procedure until stop is set or stackP has only one vertex, then push pi onto stackP. procedure cutearP(s) suppose pk is the topmost vertex on stackP followed by pk\Gamma 1. if pk\Gamma 1pks is an ear of the remaining portion of P yet to be triangulated and _(pk\Gamma 1pks) ! _(pqr) then use pk\Gamma 1pks in triangulating P ; pop pk from stackP else set stop := true endif. The triangulation is complete if, at the end of the process, there are only two vertices on stackP. Similarly, we use stackR and procedure cutearR(s) to triangulate R. 3.4.2 Analysis under (I) The above ear-cutting process speeds up the algorithm for measures satisfying (I) and (II). But, we can do better for (II) by further refinement. This is because partial effort on unsuccessfully triangulating P and R can be saved for subsequent attempts. This results in further speed up when integrated into a clever way to search for a good edge-insertion. We will return to this discussion after we analyze the current refinement. Theorem 3.2 Let S be a set of n points in R2 and let _ be a measure that satisfies (I). A triangulation of S that minimizes the maximum _ can be constructed in time O(n3) and storage O(n2). Proof. To achieve the claimed bounds, we use the algorithm above, along with two data structures requiring a total of O(n2) storage. First, the quad-edge data structure (Section 1.2) 30 stores the triangulation in O(n) storage and admits common operations, such as removing an edge, adding an edge, and walking from one edge to the next in constant time each. Second, to record the status of candidate edges, we use an n-by-n bit array whose elements correspond to the edges defined by S. If the insertion of a candidate edge qs is unsuccessful, that is, the triangulation of P or R cannot be completed, then we know by the Cake-Cutting Lemma that qs cannot be in any improvement of the current triangulation. We then set the bit for qs, so that we do not attempt the insertion of qs again. If the insertion of qs is successful, we set the bit for pr since it cannot be in any later improvement (as implied by (I) that every improvement breaks pr). The bit array is also used to compute the sequence of candidate edges: scan the row corresponding to q and take all edges qs that intersect pr and whose flags have not yet been set. Each edge-insertion, whether successful or not, causes a new flag set for one of the \Gamma n2\Delta edges defined by S. Therefore, at most \Gamma n2\Delta edge-insertions are carried out, taking a total of O(n3) time. The claim follows because an initial triangulation can be constructed in time O(n log n), most straightforwardly by plane-sweep (Section 2.1). 3.4.3 Triangulating by Ear Cutting -- Part 2 We now continue to refine the ear cutting process to triangulate P and R for measures satisfying (II). To be accurate, we should mention that the task of cutting ears and that of searching for a candidate edge are woven together. The complete algorithm is given in the next subsection. The refinement centers at saving partial work done in an unsuccessful edge-insertion of qsi\Gamma 1 to qsi. In particular, some removed ears due to qsi\Gamma 1 may remain valid for qsi = qs. Thus, we just need to restore P and R to the extent necessary and then triangulate their remaining portions on their stacks. For reason of efficiency (Section 3.4.5), we alternate removing an ear from each, and when one polygon is successfully triangulated, we attempt to complete the polygon that remains. This is formalized in the following CutEars procedure. 31 procedure CutEars stop := false; while stackP and stackR each has * 2 vertices and not stop do cutearP(s); if not stop then cutearR(s) endif endwhile; while stackP has * 2 vertices and not stop do cutearP(s) endwhile; while stackR has * 2 vertices and not stop do cutearR(s) endwhile. If the procedure finishes without raising the flag (stop = false), then we must have only one vertex on each stack, and thus the triangulations for P and R are complete and an improvement has been obtained. Otherwise, the flag is raised while testing either P or R (so we should really have used two flags to be able to distinguish the two cases--we pretend we did). Let us now consider the case where the triangulation of P cannot be completed due to the insertion of candidate edge qs. Let P 0 be the portion of P defined by vertices q = p0; p1; : : : ; pk on stackP and s = pk+1. By construction, each possible ear pj\Gamma 1pjpj+1, j ^ k of P 0 is such that _(pj\Gamma 1pjpj+1) ? _(pqr). The next lemma is crucial for defining next(s). Lemma 3.3 Let B be an improvement of A for _ satisfying condition (II). Then all edges of B that intersect the interior of P 0 also intersect qs. In particular, all edges of B incident to q avoid the interior of P 0. Proof. As in the proof of the Cake-Cutting Lemma, we consider P 0 as a "window" through which we see clipped edges of B. Now suppose the claim is not true, that is, there is at least one clipped edge with no endpoints on qs. As before we thus find such a clipped edge xy whose far side is a triangle xpjy. But now condition (II) implies _(B) ? _(pj\Gamma 1pjpj+1) if pj is an anchor of the ear pj\Gamma 1pjpj+1, and _(A) ? _(pj\Gamma 1pjpj+1) if pj\Gamma 1 or pj+1 is an anchor. This contradicts the assumption that P 0 has no such ear. It is interesting to observe that the proof of Lemma 3.3 breaks down if we assume that _ satisfies only (I). Symmetrical result holds for R0, the portion of R defined by vertices q = r0; r1; : : : ; rm on stackR and s = rm+1, when R cannot be completed due to the insertion of candidate edge qs. 32 3.4.4 Searching for a Proper Edge As we search for an edge-insertion, we maintain an open wedge W containing all the remaining candidate edges. Initially, W is the wedge between the ray ~qp and the ray ~qr. If the edgeinsertion of qsi turns out to be unsuccessful because the triangulation of P cannot be completed, then Lemma 3.3 allows us to refine W as the part of the old W on R's side of ~qsi; see Figure 3.3. Similarly, if the triangulation of R cannot be completed, then W can be narrowed down to ffl ffl q si p1 pk rm r1 P R ffl ffl ffl ffl fflffl fflffl ffl ffl Figure 3.3: The two rays define the current W , and the broken line segments indicate those triangles removed from P and R. If P is found to be noncompletable, then the next candidate edge qsi+1 lies in the updated W defined by ~qsi and the ray passing through R. P 's side of ~qsi. (As a consequence, if neither P nor R can be completed, then it is impossible to improve the current triangulation by breaking pqr at q. This, however, turns out to be too costly to check; see Section 3.4.5.) Assume that qsi has failed because P could not be completed. Because qsi+1 intersects rmsi, and thus moves away from P 0, all ears cut off P 0 remain the same and do not have to be reconsidered. On the other hand, si is no longer a vertex of R, so all ears cut off R0 that are incident to si must be returned to the territory of R0. We can now integrate the tasks of searching for a good edge-insertion and triangulating P and R. This is shown in the next procedure. The searching is done by stepping from triangle to triangle. The first vertex s that we test is the third vertex of the other triangle of pr (if no such triangle exists, then pr is an edge of the convex hull of S and no appropriate vertex s exists). In general, each subsequent s is just the third vertex of the triangle incident to pkrm where s and q lie on opposite sides of the line through pkrm. This vertex is denoted by third(pk; rm). For each new vertex s obtained in this fashion, we distinguish two cases: if s 2 W , then an 33 edge-insertion is performed; else, we remove ears as much as possible. Note that W is defined by ~qpw and ~qrw. Input. A triangulation A of S with triangle pqr so that _(pqr) = _(A). Output. An improved triangulation or a message that the measure cannot be improved. Algorithm. Set pw := p, rw := r; push q then p onto stackP , and q then r onto stackR; loop if third(pk; rm) is not defined then return the message that the measure cannot be improved and stop else set s := third(pk; rm), and remove pkrm from A; if s 2 W then add qs to A and attempt the triangulation of P 0 and R0 by CutEars case 1: The attempt succeeds. Return the new triangulation and stop; case 2: The flag was raised while testing P . Set pw := s, and push s onto stackP; restore ears cut off R0 that are incident to s; case 3: The flag was raised while testing R. Set rw := s, and push s onto stackR; restore ears cut off P 0 that are incident to s else (i.e., s 62 W ) if srm intersects W then stop := false; while not stop do cutearP(s) endwhile; push s onto stackP else (i.e., spk intersects W ) stop := false; while not stop do cutearR(s) endwhile; push s onto stackR endif endif endif forever. 3.4.5 Analysis under (II) Because of the alternation between removing an ear from P 0 and one from R0, at most only one more than half of the removed ears are restored. This is also true if one polygon is completely triangulated while ears are still removed from the other, because in this case only the ears of the former polygon need to be restored, and their number is smaller than those cut off from the 34 other. Thus, the total number of removed ears while edge-inserting qs1; qs2; : : :; qsl is linear in the number of old edges intersected by qsl, and so does the running time of the procedure. We next prove that the old edges removed will never be reinserted in any later successful edge-insertion, which then implies the claimed time-complexity of the algorithm. Lemma 3.4 Let A be a triangulation of S, with worst triangle pqr, and let B be obtained from A by the successful insertion of an edge qsl. Then no edge xy in A that intersects qsl can be an edge of any improvement of B. Proof. Lemma 3.3 implies that every improvement of B has an edge qw that lies inside the wedge W computed when qsl is inserted into A. Every edge xy in A that intersects qsl also intersects every other edge qt with t 2 W . In particular, xy " qw 6= ; which implies that xy is neither in B nor in any improvement of B. Theorem 3.5 Let S be a set of n points in R2, and let _ be a measure that satisfies (II). A triangulation of S that minimizes the maximum _ can be constructed in time O(n2 log n) and storage O(n). Proof. As before, the algorithm uses the quad-edge data structure to store the triangulation. The bit array, however, is replaced by a priority queue that holds the triangles of A ordered by measure. It admits inserting and deleting triangles and finding a triangle with maximum measure in logarithmic time each [CLR90]. Lemma 3.4 implies that only O(n2) edges and triangles are manipulated in the main loop of the algorithm, which thus takes time O(n2 log n). Lemma 3.4 also implies a quadratic upper bound on the number of iterations of the repeat-loop, which implies that the total time needed to find worst triangles pqr is also O(n2 log n). 3.5 Extensions In this section, we address the extensions to constrained problem and to problem defined by vector of measures. The Cake-Cutting Lemmas and Lemma 3.1 remain valid for constrained 35 triangulations provided the measures satisfies (I) or (II) also in this more general setting. In this case, we only need to modify the algorithm so that edges intersecting constraining edges can never be used as candidate edges for insertions. This modification does not increase the time-complexity. It follows that the unique triangulation that lexicographically minimizes the decreasing vector of triangle measures can be constructed for the non-degenerate case where no two triangles of the point set have the same measure. First, construct a min-max triangulation, T1, and declare the three edges of the triangle with the largest measure as constraining edges. Second, construct a min-max triangulation T2 for the thus constrained input and introduce new constraints to enforce the second largest measure in future triangulations. Continue this way and construct triangulations T3, T4 and so on, until the constraining edges add up to a triangulation themselves. Interestingly, the time- and storage-complexity remain the same. As before, for measures satisfying (I), it is because each edge needs to be inserted at most once during the entire process. For measures satisfying (II), each edge once removed cannot reappear in any future triangulations. We summarize the results as follows. Corollary 3.6 Let S be a set of n points in R2, with or without constraining edges. Let _ be a measure that satisfies (I). (1) A triangulation of S that minimizes the maximum _ can be constructed in time O(n3) and storage O(n2). (2) In the non-degenerate case, when _(xyz) 6= _(abc) unless xyz = abc, the triangulation that lexicographically minimizes the decreasing vector of measures _ can be constructed in the same amount of time and storage. Corollary 3.7 Let S be a set of n points in R2, with or without constraining edges. Let _ be a measure that satisfies (II). (1) A triangulation of S that minimizes the maximum _ can be constructed in time O(n2 log n) and storage O(n). 36 (2) In the non-degenerate case, the triangulation that lexicographically minimizes the decreasing vector of measures _ can be constructed in the same amount of time and storage. 3.6 Discussion The main result of this chapter is the formulation of the edge-insertion paradigm as a general method to compute optimal triangulations, and the identification of two classes of criteria for which the paradigm indeed finds an optimum. The algorithm for measures satisfying (I) appears in Sections 3.4 and 3.4.1, and for (II) in Sections 3.4, 3.4.3, and 3.4.4. Though usually simple to verify, conditions (I) and (II) are somewhat restrictive. Currently, only four measures are known to satisfy them (next chapter). It would be interesting to find conditions weaker than (I) even though the price to pay may be implementations of the paradigm that take more than cubic time. On the other hand, it remains open whether further speed up is possible for the two refinements presented. Another problem suggested in Section 3.5 is how to optimize vectors of measures in the degenerate case where multiple measures occur. We note that the special case of this problem for a simple polygon can be handled easily by dynamic programming in time O(n4) and storage O(n3). 37 Chapter 4 Applications of Edge Insertion This chapter shows four applications of the edge-insertion paradigm. The main result is the following theorem derived from corollaries 3.6 and 3.7. Theorem 4.1 For a set of n vertices S in R2, with or without constraining edges, (1) a min-max angle triangulation can be computed in time O(n2 log n) and storage O(n), (2) a max-min height triangulation can be computed in time O(n2 log n) and storage O(n), (3) a min-max slope triangulation can be computed in time O(n3) and storage O(n2), and (4) a min-max eccentricity triangulation can be computed in time O(n3) and storage O(n2). In addition, the generalization of each criterion to the vector form can be computed in the same amount of time and storage, provided the input is non-degenerate. To prove Theorem 4.1, we show that the measure _ satisfies condition (II) when defined as the largest angle or the (negative) height (Sections 4.1 and 4.2), and it satisfies (I) when defined as the slope or the eccentricity (Sections 4.3 and 4.4). In each case, the proof also holds under the more general setting with constraining edges. For these to be a worthy exposition, we must first be convinced that other known methods, especially the edge-flip scheme, fail to optimize these measures. In addition, we must ascertain that these criteria, plus the empty 38 disk property, do not necessarily define the same optima. These issues are discussed in the next few paragraphs. Recall that the edge-flip scheme iteratively flips an edge as long as it makes a local improvement. As each flip is allowed only for two abutting triangles forming a convex quadrilateral, it is highly probable that the method gets stuck in local optima. For instance, consider the triangulation of Figure 4.1 when subject to edge-flip under min-max angle, max-min height, or min-max eccentricity. It is a regular pentagon abcde that was slightly perturbed. More ffl ffl fflffl ffl a e dc b Figure 4.1: Flipping be or bd cannot locally improve this triangulation. Thus, the edge-flip scheme cannot change the shown triangulation into the optimal one containing edges ac and ad. precisely, the perturbation is such that jbcj ? jdej, "abc = "aed ! "bcd ! "cde, and also h(d; ce) ! h(c; bd) ! h(e; ad) = h(b; ac) ! h(a; be), where h(y; zx) denotes the minimum distance between y and a point on the line through zx. Take this same example, and imagine that vertices are not perturbed and thus form a regular pentagon. If we set the elevations (or data values) of a; b; c; d; e to 5; 0; 10; 0; 11 in this sequence to assign slopes to triangles, we again have a bad example for edge-flip on the slope measure. One quick way to estimate the slope of a spatial triangle ^pi ^pj ^pk given by its planar projection pipj pk (as in our example) is as follows. Assume the given elevations of the vertices are such that ssk3 * ssj3 * ssi3. If ssj3 = ssi3, then the slope is simply ssk3\Gamma ssi3h(pk;pipj). Otherwise, let z be the projection of a point on ^pi ^pk with elevation ssj3. From simple calculation, z can be computed and so does the slope ssj 3\Gamma ssi3 h(pi;zpj) . We can stretch the same example so that it is also the Delaunay triangulation of the vertices. It thus follows that Delaunay triangulation is not necessarily the same as a min-max angle, a max-min height, or a min-max eccentricity triangulation. Trivially, we can say the same for 39 Delaunay triangulations and min-max slope triangulations. Since slope and eccentricity satisfy (I) but not (II), they define different optima from largest angle and height. Lastly, each pair can be distinguished by a simple example with four vertices, and thus they are all distinct. 4.1 Minimizing the Maximum Angle A min-max angle triangulation of a point set S minimizes the maximum angle of its triangles, over all triangulations of S. As mentioned, such optimal triangulation has potential applications in finite element analysis and surface interpolation [BaAz76, BaLi84, Greg75]. For x; y; z 2 S, we define ff(xyz) = maxf"x; "y; "zg as the measure of triangle xyz. The measure of a triangulation A of S is ff(A) = maxfff(xyz) : xyz a triangle of Ag. For triangle xyz, we designate vertices y with "y = ff(xyz) as anchors. Then, the next lemma shows that ff satisfies condition (II). Lemma 4.2 Let xyz be a triangle of a triangulation A of S, and y be an anchor of xyz. Then ff(T ) ? ff(xyz) for any triangulation T of S that neither contains xyz nor breaks xyz at y. Proof. Assume that xyz is not in T and that T does not break xyz at y. Then, there exists a triangle uyv in T so that either u = x and uv " yz 6= ; (rename vertices if necessary), or uv intersects both yx and yz. In both cases, ff(T ) * "(uyv) ? ff(xyz) because "xyz is properly contained in "uyv. We thus establish part (1) of Theorem 4.1. We note that the edge-insertion paradigm actually evolved from the algorithm for min-max angle triangulations [ETW90], rather than the order materials are presented here. The Cake-Cutting Lemma was also the main idea behind the algorithm. Its original proof has a strong flavor of "cutting cake" from which the lemma gets its name. For this historical and sentimental reasons, we repeat the proof in the rest of this section. Though the proof may look slightly longer, it is conceptually simpler than the one in the previous chapter. 40 Lemma 4.3 (Cake-Cutting) Suppose triangulation T is an improvement of triangulation A. Let pqr be a triangle in A with "pqr = ff(A) but not in T , and let qs be an edge in T that intersect pr. Let P and R be the polygons generated by adding qs to A and removing all edges that intersect qs. Then there are triangulations P and R of P and R with ff(pqr) ? ff(P) and ff(pqr) ? ff(R). Proof. We prove the claim for P ; it follows for R by symmetry. As before, we lay P on top of T so that their corresponding vertices match, and called each connected component of an edge of T intersected with the interior of P a clipped edge. Again, we use these clipped edges to cut (the cake) P to obtain P. Given a point x on the boundary of P , let the path from x to q (or x to s) be the part of the boundary between x and q (or x and s) that does not contain qs. We distinguish four classes of clipped edges xy; see Figure 4.2. fflffl fflffl ffl ffl ffl ffl ffl ffl ffl q pcf i j k t u z s ab w l v mn d h g e Figure 4.2: The class I edges in this example are eg and mv; the class II edges are cj, ck, cz, and sp; the class III edges are cl and cw; and the class IV edges are jh, jd, un, zb, and sa. I. Both endpoints, x and y, are not vertices of P and thus lie on edges of P . II. Both endpoints are vertices of P . III. Endpoint x is a vertex of P , y is not, and y lies on the path from x to s. IV. The same as class III except that y lies on the path from x to q. 41 At any vertex x of P , the clipped edges with one endpoint at x define angles at x that are all smaller than ff(A), because the clipped edges come from T . The only disadvantage of the division of P defined by the clipped edges is that some of their endpoints lie on edges of P rather than at the vertices. We will now construct a triangulation of P based on the clipped edges. It proceeds step by step where each step either removes or rotates a clipped edge or introduces a new edge. 1. All class I edges are removed. This does not harm any angle. 2. All class II edges remain where they are. 3. Let xy be a class III edge with y on the edge fifl of P , where fi precedes fl on the path from x to s. We replace xy by xfl. Note first that xfl is indeed a diagonal of P . Otherwise, it intersects the boundary of P , which implies that either x or fl is not visible from qs. This is a contradiction to the way P is constructed. Note second that the angle at x that precedes xy in the counterclockwise order increases in step 3. Still, the angle formed by xfl is strictly contained in an angle at x in A because all edges of A that intersect the interior of P also intersect qs. It follows that the angle formed by xfl is smaller than ff(A). Another issue that comes up is that there can be class IV edges x0y0 with y0 on the same edge fifl of P ; these edges now intersect xfl. To remedy this situation we replace x0y0 by x0x. By the same argument as above, x0x is a diagonal of P , and the angle at x0 that precedes x0y0 in the clockwise order, and which increases as we replace x0y0 by x0x, remains smaller than ff(A). 4. If xy is a class IV edge with y on the edge fifl of P , where fi precedes fl on the path from x to q, then we replace xy by xfl. 5. After steps 1 through 4 we have a partial triangulation of P which we complete by adding edges arbitrarily. This finishes the construction of P. We have ff(P) ! ff(A) since we started out with all angles smaller than ff(A); each time an angle increases it remains smaller than ff(A) as argued above, and step 5 decomposes angles, thus creating only smaller angles. 42 4.2 Maximizing the Minimum Height Recall that the height j(xyz) of triangle xyz is the minimum distance from a vertex to the opposite edge, i.e., j(xyz) = minfh(x; yz); h(y; xz); h(z; xy)g. We write j(A) = minfj(xyz) : xyz a triangle of Ag for the measure of a triangulation A of S. A max-min height triangulation of S maximizes j(A) over all triangulations A of S. Such triangulations have been suggested for use in surface interpolation [GCR77, WaPh84]. We next show that \Gamma j satisfies condition (II), when we define vertices of xyz with largest angle to be anchors. This establishes part (2) of Theorem 4.1. Lemma 4.4 Let xyz be a triangle of a triangulation A of S, and let y be an anchor of xyz. Then j(T ) ! j(xyz) for any triangulation T of S that neither contains xyz nor breaks xyz at y. Proof. Since y is an anchor, we have height j(xyz) = h(y; zx), which is the distance between y and a point s 2 zx. Assume that xyz is not in T and that T does not break xyz at y. Then there exists a triangle uyv in T so that either u = x and uv " yz 6= ; (rename vertices if necessary), or uv intersects both yx and yz. In both cases, j(uyv) ^ h(y; uv) ! j(xyz) because uv " ys 6= ;. We insert the following paragraph on the relations of non-obtuse triangulations with some of the above optimal triangulations. These, as we will see, have some implication to the implementation of the edge-insertion algorithm. We call a triangulation non-obtuse if the sizes of all angles, three per triangle, are less than or equal to ss2 . It should be clear that not every point set S admits a non-obtuse triangulation. If T is a non-obtuse triangulation of S, then it is the Delaunay triangulation, or a completion of it in degenerate cases. This is because T is optimal with respect to the edge-flip operation. Besides those properties of Delaunay triangulations (Section 2.4), a non-obtuse triangulation T of a point set also minimizes the maximum angle since it is unique up to choosing diagonals of rectangles. The next lemma implies that T also maximizes the minimum height. 43 Lemma 4.5 If T is a non-obtuse triangulation of S, then there is no other triangulation that improves T with respect to j. Proof. We show that there is no edge whose insertion could improve T ; the Cake-Cutting Lemma then implies the assertion. Let pqr be a triangle in T with j(pqr) = h(q; rp) = j(T ), and assume there is an edge qs, with qs " rp 6= ;, whose insertion improves T . Let pqt be the triangle in the improvement that lies on the same side of the line through pq as pqr. If h(p; sq) ^ h(q; rp), then j(pqt) ^ h(p; tq) ^ h(p; sq) ^ h(q; rp) = j(pqr), a contradiction to the assumption that pqt is a triangle in the improvement of T but not in T . Therefore, h(p; sq) ? h(q; rp), and symmetrically h(r; sq) ? h(q; rp). It follows that "pqs ? "qpr and "rqs ? "qrp. But now "pqs + "rqs = "pqr ? "qpr + "qrp which can be the case only if "pqr ? ss2 , a contradiction to the assumption. Lemma 4.5 implies that during the construction of a max-min height triangulation the heights of non-obtuse triangles need not be stored in the priority queue. This is because the height of such a triangle can be smallest only if the current triangulation is already optimal. 4.3 Minimizing the Maximum Slope Consider a function f : R2 ! R defining a surface x3 = f (x1; x2) in R3. The gradient of f is the vector rf = ( @f@x 1 ; @f @x2 ), each component of which is itself a function from R2 to R. Definer 2f = ( @f @x1 )2 + ( @f @x2 )2, and call pr2f at a point (x1; x2) the slope at this point. Let S be a set of n points in R2 and let ^S be the corresponding set in R3 where each point of S has a third coordinate called elevation. For a point x of S, we write ^x for the "lifted" point, that is, the corresponding point in ^S. Analogous to the definitions in R2, ^x^y denotes the line segment with endpoints ^x and ^y, and ^x^y ^z denotes the triangle with vertices ^x; ^y; ^z. We can think of ^x^y ^z as a partial function f on R2, defined within xyz. At each point in the interior of xyz, the gradient is well defined and the same as for any other point in the interior of xyz. We can therefore set oe(xyz) equal to the slope at any point in the interior of xyz, and call it the 44 slope of xyz. For a triangulation A of S define oe(A) = maxfoe(xyz) : xyz a triangle of Ag, as usual. A min-max slope triangulation of S minimizes oe(A) over all triangulations A of S. Observe that the direction of steepest descent at any point in the interior of a triangle xyz is given by \Delta = \Gamma rf at that point. We call vertex y an anchor of xyz unless the line y + *\Delta , * 2 R, intersects the closure of xyz only at y. In the non-degenerate case, xyz has only one anchor, but if \Delta is parallel to an edge, then there are two anchors. Call the intersection of the closure of ^x^y^z with the plane parallel to the x3-axis through y + *\Delta the descent line `(xyz) of xyz, assuming y is an anchor of xyz. The remainder of this section shows that measure oe satisfies condition (I). For technical reasons it is necessary to assume that no four points of ^S are coplanar. Indeed, the strict inequality in the next lemma is incorrect without this assumption. This general position assumption, however, does not diminish the generality of our algorithm, because a simulated perturbation of the points can be used to enforce general position [EdM"u90]. This perturbation is infinitesimal. Consider the triangulation of the unperturbed points that corresponds to an optimal triangulation of the perturbed points. This triangulation must minimize the maximum slope over all triangulations of the unperturbed points. Lemma 4.6 Let xyz be a triangle of a triangulation A of S, and let y be an anchor of xyz. Then maxfoe(A); oe(T )g ? oe(xyz) for every triangulation T of S that neither contains xyz nor breaks xyz at y. Proof. The slope of xyz, oe(xyz), is also the slope of the descent line `1 = `(xyz). Assume without loss of generality that `1 descends from ^y down to where it meets the closure of ^x^z. (If it ascends, we use the same argument only with the x3-axis reversed.) Assume also that T neither contains xyz nor breaks it at y. It follows that T contains an edge uv so that either u = x and uv " yz 6= ; (rename vertices if necessary), or uv intersects both yx and yz. If oe(uyv) ? oe(xyz), then oe(T ) ? oe(xyz) and there is nothing to prove. Otherwise, the edge ^u^v must pass above `1 in R3. By this we mean that there is a line parallel to the x3-axis that meets ^u^v and `1, and the elevation of its intersection with ^u^v exceeds the elevation of its intersection with `1, as in Figure 4.3. Then at least one of ^u and ^v must lie 45 ffl ffl ffl ffl ffl ^u ^v ^y ^x ^z `1 Figure 4.3: The triangle xyz with anchor y in A is neither contained in T nor is it broken at y by T . Therefore, T contains a triangle uyv that intersects xyz as shown. It is possible that u = x or v = z, but not both at the same time. above the plane h1 through points ^x; ^y; ^z; say ^v lies above h1. Consider the triangle yvz, and note that it is not necessarily a triangle of A or T , nor even an empty triangle of S. We have oe(yvz) ? oe(xyz) because the projection (along x3-axis) of `1 onto the plane h2 through ^y; ^v; ^z is steeper than `1 but not steeper than `2 = `(yvz). We distinguish three cases depending on which vertex is the anchor of yvz, that is, through which one a line of steepest descent of ^y^v^z passes. Case 1. v is an anchor of yvz. Then `2 connects ^v with a point on the closure of ^y ^z. Consider the intersection of A with a plane parallel to the x3-axis through `2. This intersection includes a polygonal chain that connects ^v with that same point on the closure of ^y^z (since yz is an edge in A). One of the segments in the chain must have slope at least the average slope of the chain; hence one of the triangles abc in A has oe(abc) * oe(yvz) ? oe(xyz), and oe(A) ? oe(xyz). Case 2. z is an anchor of yvz. Then `2 connects ^z with a point on the closure of ^y^v. Then we use the same argument as in Case 1, only applied to T . Since yv is an edge in T at least one of the triangles abc in T that intersect the projection (along x3-axis) of `2 has oe(abc) * oe(yvz) ? oe(xyz), and therefore oe(T ) ? oe(xyz). Case 3. y is an anchor of yvz. In this case `2 connects ^y with a point ^w on the closure of ^v ^z. Furthermore, it is impossible that `2 descends from ^y to ^w because ^w lies above h1, which contradicts oe(yvz) ? oe(xyz). Thus, it must be that `2 descends from ^w down to ^y. Then oe(uyv) ? oe(yvz) because ^u^v passes above `2. But oe(yvz) ? oe(xyz), so we have shown oe(T ) ? oe(xyz). 46 This implies part (3) of Theorem 4.1. An example to show that oe indeed violates (II) is given in Figure 4.4, so an O(n2 log n) time algorithm for min-max slope triangulations seems out of reach at this moment. fflffl ffl ffl ffl ffl ^x; 0 ^z; 0 ^y; 10 ^v; 10 ^w; 9 ^u; 10 Figure 4.4: Triangulation T with diagonals uv, vw, and wu is an improvement of A with diagonals xy, yz, and zx. T has no triangle with slope as large as oe(xyz), but does not break xyz at any of its vertices. 4.4 Minimizing the Maximum Eccentricity Consider a triangle xyz and let (c1; ae1) be its circumcircle, with center c1 and radius ae1. Recall that the eccentricity of xyz, ffl(xyz), is the infimum over all distances between c1 and points in the closure of xyz. Clearly, ffl(xyz) = 0 iff c1 lies in the closure of xyz. Note that eccentricity is related to the size of the largest angle, ff(xyz). Specifically, unless ffl(xyz) = ffl(abc) = 0, ff(xyz) ! ff(abc) iff ffl(xyz)ae 1 ! ffl(abc) ae2 where ae2 is the radius of the circumcircle of abc. This suggests we call y an anchor of xyz if the angle at y is at least as large as the angles at x and z. As usual, we define ffl(A) = maxfffl(xyz) : xyz a triangle of Ag. A min-max eccentricity triangulation of S minimizes ffl(A) over all triangulations A of S (see [WaPh84]). Obviously, a non-obtuse triangulation, when it exists, for a point set S also minimizes its maximum eccentricity. Figure 4.5 shows that measure ffl does not satisfy condition (II). On the other hand, ffl does satisfy condition (I) as shown by the next lemma, which then implies part (4) of Theorem 4.1. 47 ffl ffl ffl ffl ffl ffl x z y v w u Figure 4.5: T is the triangulation with diagonals uv, vw, and wu, and A is the one with diagonals xy, yz, and zx. We have ffl(T ) = ffl(uyv). As vertices u and v lie very close to yx and yz, respectively, the circumcircle of uyv is significantly smaller than the one of xyz and ffl(uyv) ! ffl(xyz). So, T is an improvement of A, yet T does not break xyz of A at any of its vertices. Lemma 4.7 Let xyz be a triangle of a triangulation A of S, such that ffl(xyz) ? 0, and let y be an anchor of xyz. Then maxfffl(A); ffl(T )g ? ffl(xyz) for every triangulation T of S that neither contains xyz nor breaks xyz at y. Proof. Assume that T neither contains xyz nor breaks it at y. Therefore, T contains a triangle uyv so that u = x and uv " yz 6= ; (rename vertices if necessary), or uv intersects yx and yz. Let (c1; ae1) be the circumcircle of xyz. If neither u nor v are enclosed by this circle, then ffl(T ) * ffl(uyv) ? ffl(xyz). Otherwise, assume that v is enclosed by (c1; ae1) and consider the line segment c1v. It intersects a sequence of edges of A, ordered from c1 to v. For an edge ab in this sequence let abc be the supporting triangle so that c and c1 lie on different sides of the line through ab. Assume that ab is the first edge in the sequence so that (c1; ae1) encloses c but not a and not b. Then ffl(A) * ffl(abc) ? ffl(xyz). 4.5 Discussion This chapter shows that the edge-insertion paradigm can optimize the min-max angle, the maxmin height, the min-max slope and the min-max eccentricity criteria. These polynomial time solutions are the first, and currently the only ones, for these problems. An interesting side 48 result is that non-obtuse triangulations also optimize the above criteria except for the min-max slope. We remark that conditions (I) and (II) have also been tested for other measures mentioned earlier in Section 1.3. None of them seems to meet the requirements. Of course, the techniques of retriangulating regions and searching for a good edge-insertion can still serve as a heuristic that is more powerful than edge-flip when applied to these problems. Acknowledgments The results collected in the last two chapters come from several people. It all started as a course project, suggested by Professor Herbert Edelsbrunner in January 1989, studying the problem of min-max angle triangulations. Harald Rosenberger and Roman Waupotitsch first observed that four vertices are enough to distinguish min-max angle from the Delaunay triangulation. This injected some excitement to the problem. Subsequently, I took up the project and worked under the guidance of Herbert Edelsbrunner to solve the problem in time O(n8) with the basic version of the edge-insertion paradigm. Later we improved it to time O(n3) and storage O(n2) with the ear-cutting process as in Section 3.4.1. Then, Roman Waupotitsch observed that the search for a proper edge can be done efficiently by stepping from triangle to triangle, which improves the storage to linear because there is no need for a bit array that keeps track of the quadratically many possible edges. This effort leads to our subsequent discovery of the O(n2 log n) time and linear storage algorithm for the problem. This is reported in [ETW90]. The thought of formulating the solution to min-max angle triangulation into a general method was considered for some time. In December 1990, I observed that the method, with the inductive rather than the constructive proof of the Cake-Cutting Lemma, also solves the max-min height criterion in the same amount of time and storage. From there, condition (II), similar to the present form, was formulated. In June 1991, I learned from Marshall Bern (Xerox PARC) that Scott Mitchell (Cornell University) has found a similar application of the edgeinsertion paradigm to maximizing triangle heights. When Herbert Edelsbrunner visited Xerox 49 PARC in August 1991, he solved the min-max slope problem with Marshall Bern and David Eppstein (University of California, Irvine), by relaxing condition (II) to (I). Subsequently, Marshall Bern found the solution to the min-max eccentricity problem. These results are collected in [BEEMT92]. Roman Waupotitsch has implemented and experimented with most of these algorithms [EdWa92, Waup92]. The programs are currently available via anonymous ftp from the directory "/SGI/MinMaxer" at site "ftp.ncsa.uiuc.edu". 50 Chapter 5 Minimizing the Maximum Length This chapter is devoted to the study of the min-max length criterion. Generally speaking, length criteria are known to be difficult to optimize; no optimal triangulations defined on (nontrivial) length criteria has previously been computed efficiently. In the face of this apparent difficulty, the quadratic time algorithm on constructing min-max length triangulations for point sets presented here is somewhat surprising. There is evidence for the potential usefulness of such a triangulation [BrZl70, WGS90]. The developments in the forthcoming sections to solve the min-max length problem are elementary, but lengthy and occasionally involved. Some of the details contribute insight into edge length criteria. Before we continue, let us first rule out some seemingly promising approaches to computing min-max length triangulation. Note first that the Delaunay triangulation does not minimize the maximum edge length, as shown in Figure 5.1. Second, the iterative methods that use the edge-flip (Section 2.3) or the more general edge-insertion operation (Chapter 3) can get caught in local optima; see Figure 5.2. Third, the incremental greedy method, that repeatedly adds the shortest edge that does not intersect any previously added edges (see, for example, [LeLi90]), also fails to minimize the maximum edge length. For the six points in Figure 5.2, this method computes the triangulation with diagonals xy, wu, and uy. Finally, let us take a brief look at the decremental greedy method that throws away edges in the order of decreasing length. It stops the deletion process if another 51 ffl ffl ffl ffla = (\Gamma 2; 0) b = (1; p3) c = (1; \Gamma p3) d = (2 \Gamma "; 0) Figure 5.1: The length of the longest edge in the shown Delaunay triangulation approaches 2p3 the length of the longest edge in the other triangulation, as " approaches 0. Indeed, 2p3 is the worst possible ratio achieved by a Delaunay triangulation. This follows from the fact that it minimizes the radius, r, of the maximum smallest enclosing circle of all triangles [Raja91]. Hence no edge in the Delaunay triangulation exceeds 2r and every other triangulation has an edge of length at least rp3. deletion would render the set of edges so that it does not contain any triangulating subset. The trouble with this approach is that it is not clear how to efficiently decide whether the evolving edge set is still sufficient to triangulate the point set. Indeed, Lloyd [Lloy77] proves that the general version of this problem (decide whether a given edge set contains a triangulation) is NP-complete. The organization of this chapter is as follows. Section 5.1 formulates the global algorithm; its straightforward implementation using dynamic programming takes time O(n3). The only ffl ffl ffl fflffl ffl u x v yw z Figure 5.2: The diagonals are such that jxyj ! juvj = jvwj ! jwuj ! jyzj = jzxj ! juyj = jxwj ! jzvj. So, neither edge-flip nor edge-insertion can locally improve the shown triangulation A containing diagonals xy, yz and zx. However, the min-max length triangulation is not A but the one with diagonals uv, vw, and wu. 52 intricate part of this algorithm is the proof of correctness provided in Section 5.2. Sections 5.3 to 5.6 present a specialized polygon triangulation algorithm that can be used to speed up the general algorithm to time O(n2); Section 5.7 discusses implementation issues. While Sections 5.1 through 5.6 assume that the Euclidean metric is used to measure length, Section 5.8 demonstrates that all results extend to general normed metrics. Indeed, the arguments in Sections 5.1 through 5.6 are axiomatically derived from a few basic lemmas in order to minimize the number of changes necessary to generalize the results. Finally, Section 5.9 summarizes the contribution of this chapter. 5.1 The Global Algorithm Let S be a point set. We define ch(S) as the smallest convex polygon whose closure contains the convex hull of S. In the case where three or more collinear points of S lie on the boundary of this polygon, we think of each such points as a vertex of the polygon. Thus, edges are taken only between adjacent collinear points. Each edge of ch(S) is an edge of every triangulation of S, and therefore also of every min-max length triangulation. The circle with center x and radius ae is denoted by (x; ae). Recall (from Section 2.4) that rng(S) stands for the relative neighborhood graph of S, and the lune of ab is the intersection of the two disks bounded by (a; jabj) and (b; jabj). Edge set of rng(S) contains ab iff jabj ^ minx2S\Gamma fa;bg maxfjxaj; jxbjg, i.e., the lune of ab is disjoint from S. We will see in the next section that there is a min-max length triangulation mlt(S) that contains all edges of rng(S). For convenient, ch(S) and rng(S) will be interpreted as edge sets where appropriate. Because ch(S)[rng(S) is a connected graph, it decomposes the convex hull of S into simply connected regions. Though the boundary of each region is not necessarily a simple polygon, we can always treat it as one computationally (Section 1.2). Thus, we can construct mlt(S) by computing ch(S) [ rng(S) and then (optimally) triangulating each resulting simple polygon. Input. A set S of n points in R2. Output. A min-max length triangulation of S. 53 Algorithm. 1. Construct ch(S) and rng(S). 2. Determine the polygons defined by ch(S) [ rng(S). 3. Find a min-max length triangulation for each such polygon. Step 1 can be carried out in time O(n log n) using results documented in [PrSh85, Supo83]. Using the quad-edge data structure of Guibas and Stolfi (Section 1.2) for storing the plane geometric graph ch(S) [ rng(S), step 2 can be accomplished in time O(n). Then, at step 3, we can use dynamic programming (Section 2.2) to compute an optimal triangulation for each polygon in time cubic and storage quadratic in the number of its vertices. This adds up to time O(n3) and storage O(n2). The correctness of the algorithm is established next. 5.2 The Subgraph Theorem The main result of this section is what we call the Subgraph Theorem mentioned earlier. We begin with two elementary lemmas about distances between four points in convex and in nonconvex position. 2-Lemma. For a convex quadrilateral abcd, we have jabj + jcdj ! jacj + jbdj. Proof. Let x be the intersection point of the two diagonals, ac and bd. Clearly, jabj + jcdj ! (jaxj + jxbj) + (jcxj + jxdj) = jacj + jbdj. In words, the total length of the two diagonals of a convex quadrilateral always exceeds the total length of two opposite edges. This is true even if three of the four vertices are collinear. It implies that if one diagonal is no longer than one of the edges, then the other diagonal is longer than the opposite edge. \Delta -Lemma. Let a; b; c; d be four distinct points so that the closure of the triangle abc contains d. Then jadj ! maxfjabj; jacjg. Proof. If a; b; c; d are collinear the result is obvious. Otherwise, let d0 be the intersection of the edge bc with the line through ad, and note that jadj ^ jad0j. Of all points on bc [ fb; cg, only the endpoints (b and c) can possibly maximize the distance to a. The assertion follows because if d0 is an endpoint of bc, then d 6= d0 and therefore ad is strictly shorter than ad0. 54 Note that the length of the longest edge of any minimum spanning tree is no longer than the longest edge of any triangulation of S. This follows trivially from the fact that every triangulation contains a spanning tree. It is not very difficult to prove that the same is true for the relative neighborhood graph of S. Note that the bisector of two points p and q is the set of points equidistant to both. Length Lemma. Every triangulation of S contains an edge that is at least as long as the longest edge of rng(S). Proof. Let pq be the longest edge of rng(S) and let A be an arbitrary triangulation of S. If pq 2 A, there is nothing to prove. Otherwise, pq intersects edges r1s1; r2s2; : : : ; rksk of A, sorted from p to q, with all ri on one side of the line through pq and all si on the other. If pq is longer than all edges in A, then r1 and s1 are both inside the circle Cp = (p; jpqj), because pr1 and ps1 are both edges of A. By the definition of rng(S), r1 and s1 are thus outside or on the circle Cq = (q; jpqj). Therefore, r1 and s1 lie in the half-plane of points closer to p than to q. Symmetrically, rk and sk lie inside Cq and outside or on Cp and therefore in the half-plane of points closer to q than to p. For each 1 ^ i ^ k \Gamma 1, we have either ri = ri+1 or si = si+1, which implies that there is an index j so that rj and sj do not lie on the same side of the bisector of pq. But then the 2-Lemma implies that jrjsj j ? jpqj, because jpqj is no longer than each of two opposite edges of the convex quadrilateral prjqsj , a contradiction. The proof of the Subgraph Theorem is similar to that of the Length Lemma, although considerably more involved. The basic idea is to assume an extremal counterexample and to contradict its existence by retriangulating parts of it using no long edges. In the following, we first develop three facts showing the possibilities of retriangulations, and then prove the theorem. Let T be a min-max length triangulation of S that does not contain some edge pq of rng(S). Suppose pq intersects the triangles t1; t2; : : :; tk of T , sorted from p to q (see Figure 5.3 left). The deletion of the edges that intersect pq would result in a simply connected region, whose boundary can be interpreted as a simple polygon--we treat each edge in its boundary as a pair of edges with opposite directions, and to trace the boundary of the region we traverse all directed edges that have the region on their left side. Any two consecutive (directed) edges 55 p qffl ffl ffl ffl fflfflffl ffl p q=c0ffl ffld ffld0 ffl fflb 0fflb; a0 fflaffl c p qffl ffl ffl ffl fflffl ffl ffl Figure 5.3: To the left we see the triangles of T that intersect pq. If we remove the edges intersecting pq we get a polygon whose boundary is oriented in a counterclockwise order. The prefix P and the suffix Q defined for this configuration are illustrated to the right. Although b and a0 are the same point, they refer to different angles of this point. define an angle (see Figure 5.3 middle). Note that a vertex can correspond to many angles, although the common situation is that it corresponds only to one. We will therefore sometimes ignore the difference between vertices and corresponding angles. Points p and q correspond to only one angle each. An angle is convex if the two defining edges form a left turn. Call the sequence of edges from p to q the lower chain and the sequence from q to p the upper chain. Each chain contains at least one convex angle different from p and q. A prefix is an initial subsequence of t1; t2; : : : ; tk, and a suffix is a terminal subsequence of t1; t2; : : : ; tk. We say that a prefix (suffix) covers an angle of the polygon if it contains all triangles incident to this angle. Let i be minimal so that the prefix P = t1; t2; : : : ; ti covers a convex angle other than p, and let j be maximal so that the suffix Q = tj; tj+1; : : : ; tk covers a convex angle other than q. P and Q consist of at least two triangles each. We let b be the convex angle (vertex) covered by P --it is incident to both ti and ti\Gamma 1--and d be the other vertex common to ti and ti\Gamma 1. Furthermore, c is the third vertex of ti\Gamma 1 and a is the third vertex of ti (see Figure 5.3 right). Symmetrically, define vertices b0; d0; c0; a0 of Q. We say that P (Q) is type 1 if the last (first) two triangles of P (Q) are the only ones incident to b (b0), and it is type 2, otherwise (see Figure 5.4). If P is type 1, then a; b; c belong to the same chain and d belongs to the other chain (this includes the case that c = p), and if P is type 2, then a; b belong to one chain and c; d to the other. Fact 5.1 P = t1; t2; : : :; ti and Q = tj ; tj+1; : : : ; tk share at most two triangles, that is, i\Gamma 1 ^ j. 56 p type 1 ffl ffl ffl ffld fflaffl b fflcffl q type 2 fflffl fflc 0ffl d0 ffla0 ffl b0 ffl Figure 5.4: The prefix P with vertices a; b; c; d and the suffix Q with vertices a0; b0; c0; d0 are defined depending on pq. P is type 1 and Q is type 2. For illustration purposes the constraint that all vertices must lie outside the lune of pq has been ignored. Proof. We show that the suffix R = ti\Gamma 1; ti; : : : ; tk covers at least one convex angle other than q, so Q cannot be bigger than R. If P is type 1, then R covers b, which is convex. Otherwise, R covers all angles between d and q, d included. Since all angles between p and d, p and d excluded, are non-convex, at least one angle between d and q must be convex, and this angle is covered by R. It should be clear that abcd and a0b0c0d0 are both convex quadrilaterals by the choice of their vertices. The next two facts imply that either abcd, or a0b0c0d0, or both have alternate triangulations using ac or a0c0, while maintaining the maximum edge length of T . In other words, bd, or b0d0, or both can be switched. Formally, we call bd (b0d0) switchable if ac (a0c0) is no longer than the longest edge of T . Fact 5.2 shows strong locality constraints for a and d (a0 and d0) if bd (b0d0) is not switchable. Define A = fx 2 R2 : jxpj ? jpqj and jxpj ? jxqjg and D = fx 2 R2 : jxpj * jpqj and jxqj ! jpqjg; with the understanding that A and a belong to one half-plane defined by the line through pq, and D and d belong to the other (see Figure 5.5). Fact 5.2 If bd is not switchable, then a 2 A and d 2 D. Proof. Since bd is not switchable, ac must be longer than the other five edges defined by a; b; c; d, and, by the Length Lemma, it must be longer than pq. We first show that jacj ^ japj and then derive the four inequalities needed to establish the claim. 57 ffl fflp q D A Figure 5.5: The regions A and D as defined for the case when a is on the upper chain. (i) jacj ^ japj. We can assume that c 6= p. Note that c is contained in the closure of bdp. Since the line through bd separates a from p, the closures of abp and adp cover bdp completely, and therefore one of them contains c. If c lies in the closure of abp, the claim follows from jabj ! jacj and the \Delta -Lemma for abp, and if c lies in adp, it follows from jadj ! jacj and the \Delta -Lemma for adp. (ii) japj ? jpqj. This follows from (i) and jacj ? jpqj implied by the Length Lemma. (iii) jdqj ! jpqj. Assume jdqj * jpqj. The 2-Lemma for paqd implies jadj ? japj, and thus jadj ? jacj because of (i), a contradiction. (iv) jdpj * jpqj. This is immediate from (iii) because pq is an edge of rng(S). (v) japj ? jaqj. Assume japj ^ jaqj. By the 2-Lemma for paqd and (iv), we get jadj ? jaqj. This implies jadj ? japj by assumption, and jadj ? jacj by (i), a contradiction. The proof of Fact 5.2 is now complete because (ii) and (v) are equivalent to a 2 A and (iii) and (iv) are equivalent to d 2 D. Symmetrically, we define regions A0 and D0 which is where a0 and d0 must lie if b0d0 is not switchable. Using Facts 5.1 and 5.2 we can now show that there is always an edge that can be switched. Fact 5.3 It is not possible that both bd and b0d0 are non-switchable. 58 Proof. If bd and b0d0 are both non-switchable, then ad lies on q's side of the bisector of pq and a0d0 lies on p's side, by Fact 5.2. Because of Fact 5.1 and because ad is the last edge of P and a0d0 is the first edge of Q, we have fa; d; a0; d0g = fa; b; c; dg = fa0; b0; c0; d0g. Furthermore, the fact that bd and b0d0 are both edges of T implies that they are the same and thus b = d0, d = b0, a = c0, c = a0 (see Figure 5.6). It follows that the polygon has the shape of a diamond p q c=a0 d=b0 a=c0 b=d0 ffl ffl ffl ffl ffl ffl Figure 5.6: If bd and b0d0 are both non-switchable, then b and d are the only convex angles besides p and q. with p; b; q; d as the only convex angles. This contradicts the locality constraints for a; b; c; d stated in Fact 5.2. In particular, the chain from p to d 2 D is concave or straight and therefore enclosed by the circle (q; jpqj). It follows that this chain is disjoint from A0, which is where c = a0, the predecessor of d in this chain, is supposed to lie. With the above results and notations, we now choose an extremal counterexample to prove the main result of this section. Subgraph Theorem. Every point set S in R2 has a min-max length triangulation mlt(S) so that rng(S) ` mlt(S). Proof. We assume there is a set S so that no min-max length triangulation contains rng(S). Let T be a min-max length triangulation of S that satisfies the following extremal properties, where later properties are contingent upon earlier ones. (1) T minimizes the number of edges that intersect pq. (2) T minimizes the number of edges incident to b that intersect pq. (3) T minimizes the number of edges incident to b0 that intersect pq. 59 It is conceivable that T is not unique, but it will be sufficient to assume that T is any one of the remaining triangulations. By Fact 5.3, either bd, or b0d0, or both are switchable. If bd is switchable and P is type 1, then the number of edges that intersect pq decreases when bd is switched. This contradicts property (1). Thus, P must be type 2 if bd is switchable, and, similarly, Q must be type 2 if b0d0 is switchable. When we switch bd the degree of b decreases, which contradicts property (2). Thus, it must be that bd is not switchable and b0d0 is. But switching b0d0 decreases the degree of b0, which would contradict property (3), unless the degree of b increases at the same time. Remember that (3) is contingent upon (2), so if (2) is not satisfied any more, then we cannot draw any conclusion. Thus, the configuration left for analysis is as shown in Figure 5.7. p q c0 d=d0 a=b0b=a0 ffl fflffl fflffl ffl Figure 5.7: In the final configuration bd is non-switchable, so a 2 A and d 2 D, and b0d0 is switchable, so Q is type 2. Furthermore, switching b0d0 to a0c0 increases the degree of b, so a0 = b and therefore P and Q overlap in exactly one triangle. The figure ignores that by rights all points should lie outside the lune of pq. To reach the final contradiction, we switch b0d0 and redefine Q based on the new configuration. Since all angles from (the old) d0 to q are non-convex, the new points b0 and a0 are the same as before, and the new d0 is the old c0. Thus, we can again switch b0d0, and so on, until Q is type 1 or c0 = q at which point the next switch decreases the number of edges intersecting pq. This finally contradicts property (1). 5.3 Preliminaries Results on rng-Polygons This section introduces some notations, and presents a few elementary lemmas for our subsequent discussion to speed up the cubic time algorithm (Section 5.1) to quadratic time by a specialized polygon triangulation algorithm. Recall that the first two steps of the algorithm 60 decompose the convex hull of S into simply connected regions by drawing all edges of ch(S) and rng(S); these steps remain unaltered. Each region is represented by a polygon, termed an rngpolygon, with directed edges that trace the boundary of the region in a counterclockwise order around the region. Because rng(S) is a connected graph that spans S, any rng-polygon has at most one edge not in rng(S); this edge is in ch(S) \Gamma rng(S). We call an rng-polygon a complete rng-polygon if all its edges belong to rng(S), and an incomplete rng-polygon, otherwise. Obviously, rng-polygons are not as general as arbitrary polygons because for each edge ab, except possibly for one, the lune of ab, *ab = fx 2 R2 : maxfjaxj; jbxjg ! jabjg, is free of points of S. We call pq a diagonal of an rng-polygon if it lies entirely in the interior of the rng-polygon. For each diagonal pq of an rng-polygon it must be that *pq contains at least one point of S. We further distinguish between the cases where *pq contains points of S on both sides of the line through pq and where it does not. For a directed edge ~pq, let h ~pq be the set of points to the left of or on the directed line that passes through p and q in this order. Define the half-lune of ~pq as j ~pq = *pq " h ~pq: By definition, *pq = j ~pq [ j ~qp, and we have pq 2 rng(S) iff j ~pq " S = j ~qp " S = ;. We call pq an rng-edge if pq 2 rng(S), call it a 1-edge if only one half-lune contains points of S, and call it a 2-edge if both half-lunes contain points of S. For a 1-edge pq, we say the side where the half-lune contains points of S is beyond pq, and the other side is beneath pq. Note for example that if pq is a 1-edge bounding an incomplete rng-polygon R, then pq 2 ch(S) and therefore R is beyond pq. We will see later that 1-edges are useful in triangulating rng-polygons. The first lemma of this section shows that when we triangulate an rng-polygon R, whether complete or incomplete, we can ignore all points outside R. More specifically, it shows that the type of any diagonal or edge of R remains unchanged when we remove all points of S that are not vertices of R. Reduction Lemma. Let pq be a diagonal or edge of an rng-polygon R. If j ~pq contains points of S, then it also contains vertices of R. 61 Proof. Suppose j ~pq contains points of S but no vertices of R. Then, it must intersect edges of R without containing their endpoints. Let yy0 be the edge closest to p and q, and let x be a point in j ~pq " S. Since x is not a vertex of R it must lie on the other side of yy0, as seen from p and q. So yy0 2 rng(S) \Gamma ch(S), and therefore maxfjxyj; jxy0jg * jyy0j. Assume without loss of generality that jxyj * jyy0j. If y0 lies outside or on the circle (p; jpqj), we consider the convex quadrilateral pyxy0. Otherwise, y0 lies outside or on (q; jpqj), in which case we consider the convex quadrilateral qyxy0. But now we have jxyj * jyy0j and either jpy0j ? jpxj or jqy0j ? jqxj, a contradiction to the 2-Lemma in both cases. Using the Reduction Lemma, we now address vertices visible from both endpoints of an edge. We need some terminology. Two points x; y inside or on the boundary of an rng-polygon are visible from each other if xy is contained in the interior of the rng-polygon. The distance of a point x to an edge pq is defined as the infimum, over all points z 2 pq, of jxzj. If jpqj ? maxfjpxj; jqxjg, then this distance is indeed the height of triangle pqx. Visibility Lemma. Let pq be a diagonal or edge of an rng-polygon R, and let x be a vertex of R that lies in j ~pq and minimizes the distance from pq. Then x is visible from p and also from q. Proof. Consider the triangle pqx, let x0 2 pq be the point with minimum distance from x, and assume without loss of generality that x is not visible from q. Let yy0 be an edge of R that intersects qx. The proof of the Reduction Lemma implies that at least one endpoint of yy0 lies in j ~pq, say y 2 j ~pq. In addition, y and y0 lie outside pqx because x is closest to pq (see Figure 5.8). Hence, yy0 intersects xp, xq and all edges xz with z 2 pq. Thus, xyx0y0 is a convex quadrilateral, and because of jyx0j * jxx0j by the choice of x, we have jyy0j ? jxy0j from y0y p fflffl ffl ffl ffl q x x0 Figure 5.8: The quadrilateral xyx0y0 is convex because x0 2 pq and y; y0 62 pqx. 62 the 2-Lemma. By symmetry, if y0 lies in j ~pq we have jyy0j ? jxyj, which implies yy0 62 rng(S). This is a contradiction because yy0 62 ch(S). Thus, y0 must lie outside j ~pq. If y0 lies outside or on the circle (p; jpqj), then jpy0j ? jpxj, and therefore jxyj ! jyy0j by the 2-Lemma for py0xy. Symmetrically, we get jxyj ! jyy0j from the 2-Lemma for qy0xy if y0 lies outside or on the circle (q; jpqj). Together with jxy0j ! jyy0j, this contradicts yy0 2 rng(S). We need one more elementary lemma. Containment Lemma. If x 2 j ~pq, then j ~xp ` *pq. Proof. Take a point z 2 j ~xp and consider the four points p; q; x; z. If z 2 pq, there is nothing to prove. Otherwise, pzqx or pqzx is a convex quadrilateral (possibly with three of the four vertices collinear) or z 2 pqx. In each case jqzj ! jpqj can be shown using the 2- or the \Delta -Lemma. This implies z 2 *pq. The following lemma is of fundamental importance to the quadratic time triangulation algorithm. 1-Edge Lemma. Let pq be a 1-edge of an rng-polygon R, and let x be a vertex of R that lies in j ~pq and minimizes the distance from pq. Then px is either an edge of R or a 1-edge with pqx beneath px, and the same is true for qx. Proof. We have j ~xp ` *pq by the Containment Lemma. The part of j ~xp in j ~qp contains no point of S because j ~qp " S = ; by assumption. Also, the part of j ~xp in j ~pq also contains no point of S because a point y 2 j ~xp " j ~pq would be closer to pq than x is, as can be shown using the 2-Lemma for px0yx (see Figure 5.9). So px is an edge of R if j ~px contains no point of S either, and it is a 1-edge with triangle pqx on its beneath side, otherwise. The argument for qx is symmetric. 5.4 Triangulating Incomplete rng-Polygons The above lemmas are sufficient for efficiently triangulating an incomplete rng-polygon. As defined earlier, all edges of an incomplete rng-polygon R are rng-edges, except for one 1-edge, 63 ffl ffl ffl p q x x0 ffly Figure 5.9: Vertex x is visible from p and from q, so pqx is empty. It follows that if y 2 j ~xp " j ~pq, then pqyx is a convex quadrilateral. pq 2 ch(S) \Gamma rng(S), which has R on its beyond side. The algorithm below can triangulate more general incomplete rng-polygons, that is, it is not necessary that pq 2 ch(S), but it must be that pq is a 1-edge and R lies beyond pq. Input. An incomplete rng-polygon R that lies beyond its 1-edge pq. Output. A min-max length triangulation of R. Algorithm. 1. Find a vertex x in *pq that minimizes the distance from pq. 2. Draw edges px and qx. This decomposes R into the triangle pqx, and two possibly empty incomplete rng-polygons R1 and R2. 3. Recursively triangulate R1 and R2. The correctness of this algorithm follows from the 1-Edge Lemma. Indeed, it implies that if R1 is non-empty, then it lies beyond px, which is the only 1-edge of R1. Similarly, R2 lies beyond its 1-edge qx, provided R2 is non-empty. Thus, the input invariant is maintained all the way through the recursion. This implies that the algorithm successfully triangulates. By the choice of point x, the edges px and qx are both shorter than pq. It follows that the diagonals are monotonely decreasing in length, down a single branch of the recursion, and therefore all diagonals constructed by the algorithm are shorter than pq. A straightforward implementation of the algorithm takes time quadratic in the number of vertices of R. Remark. Instead of choosing a vertex x that minimizes the distance to pq, step 1 of the algorithm could also choose other vertices as long as they are visible from p and q and lie in their lune. An interesting choice among these vertices is the vertex y that minimizes maxfjypj; jyqjg. As long as y is unique, which is the non-degenerate case, this choice leads to a triangulation 64 of the polygon R that lexicographically minimizes the non-increasing vector of edge lengths. Another possible choice is the vertex z that minimizes jzpj + jzqj. This vertex is automatically visible from p and from q and might be useful in actual implementations because it is often considerably less expensive to compute the distance between two points than between a point and a line segment. 5.5 A Lemma on Polygon Retriangulation This section presents a technical lemma on retriangulating a polygon. It will find application in the next section, and is also of independent interest. In order to conveniently distinguish between boundary and non-boundary edges of a triangulation, we call a non-boundary edge a diagonal . Let X be a polygon, X a triangulation of X, and xx0 a diagonal of X that is not in X . We say that xx0 generates X if it intersects every diagonal of X . We give an algorithmic description of a particular triangulation of X, called the fan-out triangulation Fx(X) with (fan-out) center x. The triangulation is illustrated in Figure 5.10. fflx ffl ffl fflffl y0fflffl x0ffl ffl u fflw ffl y fflv Figure 5.10: The polygon X is triangulated by fanning out from x, connecting adjacent neighbors of x, and recursing in the thus created pockets. The illustration of this process is schematic and ignores some of the inherent shape constraints for X. 1. Connect x to all vertices of X that are visible from x. Call these vertices and also the two vertices connected to x by edges of X neighbors of x. 2. Two neighbors of x are said to be adjacent if they are consecutive in the angular order around x. Connect any two adjacent neighbors u; v of x, unless uv is an edge of X. 3. Every edge uv created in step 2 decomposes X into two parts, and the part that does not contain x is called the pocket Xuv of uv. Assume that u is the endpoint of uv so that the 65 other incident edge of the pocket, uw, is partially visible from x. Recursively construct the fan-out triangulation of Xuv with center v. We need a few more terminology. Among the diagonals of Fx(X), we distinguish between fan-out edges constructed in step 1 and cut-off edges constructed in step 2 of the above algorithm. Each call of the algorithm triangulates part of a pocket and recurses in each component (pocket) of the remainder. We call a pocket V a child of another pocket Z if V ae Z and V is maximal. The original polygon, X, is also called a pocket and forms the root of the tree defined by the child relation. This tree is exactly the recursion tree of the algorithm. Each pocket Z is associated with a fan-out center z. The maximum distance between z and any other vertex of Z is called the width of Z. The lengths of the diagonals of Fx(X) are constrained by the length of the longest edge of X, the length of the longest diagonal of X , and the width of X. Specifically, we prove the following result. Fan-Out Lemma. Let X be a polygon, with ffi1 the length of its longest edge, let X be a triangulation of X, with ffi2 the length of its longest diagonal, let xx0 be a generator of X , and let ffi3 exceed the maximum distance of x from any vertex of X. Then jabj ! maxfffi1; ffi2; ffi3g for every diagonal ab of Fx(X). Proof. Note that the assertion follows if we prove that maxfffi1; ffi2; ffi3g exceeds the width of every pocket Z created during the algorithm. To see this, notice that the width of Z is an upper bound on the length of any fan-out edge emanating from the center of Z. Each cut-off edge uv that creates a child pocket V of Z is incident to the fan-out center of V , which implies that the width of V is an upper bound on its length. The proof of the upper bound on the widths of all pockets proceeds inductively, from the top to the bottom of the tree. The width of X is less than ffi3, by assumption, and therefore also less than maxfffi1; ffi2; ffi3g. For the inductive step, consider a pocket Z and a child V of Z. We show that the bound on the width of Z is inherited by V , with some environmental influence from X and X . Let z be the fan-out center of Z, ffi the width of Z, v the fan-out center of V , uv the cut-off edge that creates V , and w the other vertex of V adjacent to u. 66 First, we prove juvj ! maxfffi1; ffig. By definition of fan-out center, v lies in the closure of uwz. The \Delta -Lemma thus implies juvj ! maxfjuwj; juzjg, and we get the claimed inequality because juwj ^ ffi1 and juzj ^ ffi. Second, we show that maxfffi2; ffig exceeds the maximum distance between v and any vertex of V other than u. Let y 6= v; u be such a vertex and let yy0 be a diagonal of X that intersects xx0. Such a diagonal exists because xx0 generates X . It follows that yy0 intersects uv and that therefore v lies in the closure of yy0z. Using the \Delta -Lemma, we get jyvj ! maxfjyy0j; jyzjg ^ maxfffi2; ffig because jyy0j ^ ffi2 and jyzj ^ ffi. The two bounds together imply that the width of V is less than maxfffi1; ffi2; ffig, and induction shows that it is less than maxfffi1; ffi2; ffi3g. In Section 5.6.3, we will need a result as given in the Fan-Out Lemma, but restricted to the fan-out triangulation on one side of the generator. Specifically, we need the following corollary whose proof is almost the same as the one of the Fan-Out Lemma. Fan-Out Corollary. Suppose W is a polygon, W a triangulation of W , xx0 a generator of W, and X the part of W on one side of xx0. Let ffi1 be the length of the longest edge of X, ffi2 the length of the longest diagonal of W, and let ffi3 exceed the maximum distance of x from any vertex of X. Then jabj ! maxfffi1; ffi2; ffi3g for every diagonal ab of Fx(X). Remark. The Fan-Out Lemma can also be formulated without the assumption of an initial triangulation. The condition on the diagonal xx0 is now that each vertex of X must be visible from some point of xx0. The parameter ffi2 needs to be redefined as the maximum, over all vertices y of X, of the infimum, over all points a of xx0 visible from y, of the distance between y and a. 5.6 Triangulating Complete rng-Polygons This section shows how to triangulate a complete rng-polygon R in quadratic time. The algorithm is given in Section 5.6.1. The basic idea is to divide R into two polygons, each can be triangulated by the algorithm for incomplete rng-polygons (Section 5.4). This idea is supported by the 2-edge Lemma in Section 5.6.2. That is, when vertices are in general position, there exists a min-max length triangulation of R that contains exactly one 2-edge, say pq. Moreover, 67 pq indeed divides R into two polygons that behavior as required, and the resulting triangulation thus has pq as its longest edge. Such a 2-edge can, fortunately, be computed in quadratic time as shown in Section 5.6.3. The algorithm thus has the claimed time-complexity. 5.6.1 The Algorithm We assume that no two diagonals and edges of the rng-polygon R are equally long. If this nondegeneracy assumption is not satisfied, it is necessary to run the algorithm with a simulation of non-degeneracy. The side-effects of this simulation and how they can be undone will be discussed in Section 5.7. Let us call a 2-edge pq expandable if there are vertices r and s in *pq, on different sides of the line through pq and both visible from p and q, so that E = fpr; qr; ps; qsg is a set of rngand 1-edges and the quadrilateral prqs lies beneath the 1-edges in E. The algorithm as shown computes the shortest expandable 2-edge pq (steps 1 to 3), and then completes the triangulation using the algorithm for incomplete rng-polygons (step 4). The resulting triangulation uses no 2-edge other than pq, which is thus the longest edge of the triangulation. Input. A complete rng-polygon R. Output. A min-max length triangulation of R. Algorithm. 1. Determine the type of each diagonal pq of R. 2. For each 2-edge pq, find vertices p0; p00; q0; q00 that minimize the counterclockwise angles "p0pq; "qpp00; "q0qp; "pqq00, contingent upon pp0; pp00; qq0; qq00 being rng-edges or 1-edges with pq on their beneath sides (see Figure 5.11). 3. Find the shortest 2-edge pq for which pp0; qq0; pp00; qq00 are such that p0 = q00 or pp0 " qq00 6= ;, and p00 = q0 or pp00 " qq0 6= ;. 4. As pq is expandable (Section 5.6.3), find E = fpr; qr; ps; qsg and then triangulate the (possibly empty) incomplete rng-polygons defined by pr; qr; ps; qs. Below we give the algorithmic details of the above steps. Step 1: classifying diagonals. For each vertex p of R, we compute all incident diagonals pq and their angular order around p. Furthermore, we determine whether or not the half-lune j ~pq 68 ffl ffl ffl ffl ffl ffl p q q0 p0 p00 q00 Figure 5.11: By the choice of p0 the counterclockwise angle "p0pq contains no 1-edge with pq on its beneath side. Symmetric statements hold for p00, q0, and q00. contains any vertex of R. Recall that, by the Visibility Lemma, j ~pq contains a vertex visible from p if it contains a vertex of R at all. We can thus base the decision whether or not j ~pq is empty of vertices solely on the vertices visible from p. As defined earlier, pq is a 2-edge if both half-lunes of pq contain vertices of R. Otherwise, pq is a 1-edge and its beyond side is where the half-lune contains vertices of R. We now show that the computation for p can be done in time linear in the number of vertices. It follows that quadratic time suffices for step 1. Computing the sorted sequence of diagonals pp1; pp2; : : : ; ppm incident to p is a standard operation for simple polygons and can be done in linear time; see, for example, [ElAv81, JoSi87, Lee83]. Let pp0 and ppm+1 be the two edges of R incident to p and assume that p0; p1; p2; : : :; pm+1 is in a counterclockwise order around p. To determine whether there is a vertex of R in the half-lune j ~ppi for 1 ^ i ^ m, we scan the list p0; p1; : : : ; pm+1 once, from smallest index to largest. During the scan, we maintain a stack of diagonals ppl whose half-lunes j ~ppl are not yet found to contain any vertex of R. Before pushing ppi onto the stack, we remove all diagonals ppl whose half-lunes contain pi. Using a straightforward extension of the Containment Lemma, we can show that the order of processing implies that the edges whose half-lunes contain pi lie on top of the ones whose half-lunes do not contain pi. Thus, the former can be removed simply by repeatedly popping the topmost diagonal. When the scan is complete, the stack contains exactly all diagonals ppl whose halflunes contain no vertex of R. Since a diagonal can be pushed and popped only once each, the entire process takes constant time per diagonal. Step 2: finding rng- and 1-edges. For each vertex p, we scan pp1; pp2; : : : ; ppm in this order. In the process, we keep track of the most recent rng-edge or 1-edge p_p whose beneath side is in the direction of the scan. Initially, p_p = pp0. When a 2-edge pq is encountered, then p_p is the 69 edge pp0 that belongs to pq. A symmetric scan is carried out to find the edge pp00 that belongs to pq. The total time, for all vertices p of R, is clearly quadratic. Step 3: locating shortest expandable 2-edge. Step 3 is computationally trivial. It takes quadratic time since constant time suffices to test whether or not pp0; pp00; qq0; qq00 satisfy the conditions of step 3. However, it is not trivial to see that the edge pq obtained by step 3 is also the shortest expandable 2-edge. We defer the proof till Section 5.6.3. Step 4: triangulating incomplete rng-polygons. It should be clear that we can simply scan through the vertices of R once to obtain E, then apply the algorithm for incomplete rngpolygons (Section 5.4). This step takes time only quadratic in the number of vertices of R. Incidentally, pq is in fact a 1-edge when restricted to only one of the two polygons. So, the step can actually be simplified to only two applications of the algorithm for incomplete rng-polygons. The next two subsections show the correctness of the above procedure. 5.6.2 Triangulating by One 2-Edge Under the non-degeneracy assumption, we note that every triangulation of R, and therefore also every min-max length triangulation, contains a 2-edge. To see this, consider the longest edge pq of a triangulation. It cannot be an edge of R because the third vertex of the incident triangle lies in its lune *pq. It is therefore a diagonal with incident triangles pqr and pqs, and we have r; s 2 *pq by maximality of pq. Since r and s lie on different sides of the line through pq, it follows that pq is indeed a 2-edge. In fact, we have the following stronger result utilized by the above algorithm. 2-Edge Lemma. Let R be a complete rng-polygon with no two diagonals or edges of the same length. Then there exists a min-max length triangulation of R that contains an expandable 2-edge. Proof. We assume there is no min-max length triangulation of R that contains an expandable 2- edge. A contradiction to this assumption will be derived using an min-max length triangulation of R, R defined as follows. Let pq be the longest edge of R and let pqr and pqs be the incident triangles. By the non-degeneracy assumption, pq is the longest edge of every min-max length 70 triangulation of R. Choose R so that the sum of heights of pqr and pqs (that is, the distance of r from pq plus the distance of s from pq) is a minimum. We prove below that pq is expandable and that r and s are witnesses thereof, that is, the quadrilateral prqs lies beneath every 1-edge in E = fpr; qr; ps; qsg. Case 1. Assume that prqs lies beyond at least one 1-edge in E, say beyond pr. Then we can retriangulate R on this side of pr using the algorithm for incomplete rng-polygons. Among others, this algorithm removes edge pq, and all new edges are shorter than pr, which itself is shorter than pq. This contradicts the assumption that R is a min-max length triangulation. Case 2. Assume that one of the edges of E, say pr, is a 2-edge, and assume without loss of generality that r 2 j ~pq. Thus, there is a non-empty set of vertices z of R contained in the half-lune j ~rp. By the Containment Lemma, these vertices z lie in *pq, and by the Visibility Lemma, a non-empty subset S0 of the z are visible from both p and r. If a vertex z is in S0, then either pz " rq 6= ; or rz " pq 6= ;; see Figure 5.12. Let S0p be ffl ffl ffl p q r Figure 5.12: The points z lie in the interior of j ~rp \Gamma pqr, which consists of one or two connected components depending on whether or not the angle at r in pqr is non-acute. the subset of vertices z of the first kind, and let S0r be the subset of vertices of the second kind. If S0p 6= ;, choose x 2 S0p so that the number of edges of R that intersect px is a minimum. Next, remove all edges from R that intersect px and denote by X the polygon thus generated. If, on the other hand, S0p = ;, then choose x 2 S0r 6= ; so that the number of edges in R that intersect rx is a minimum; again remove all edges from R that intersect rx, and denote the resulting polygon by X. For convenient reference, we set x0 = p in the first case and x0 = r in the second. In either case, we construct a retriangulation Fx(X) of X by fanning out from x, as described in Section 5.5. 71 We show below that the new triangulation of R has properties that contradict the assumptions of case 2. Most importantly, the Fan-Out Lemma of Section 5.5, together with a few claims which we are about to prove, imply that the edges of Fx(X) do not exceed pq in length. Claim 1. Except for x, all vertices of X lie outside the half-lune j ~rp. Proof (of Claim 1). Let y1y2; y3y4; : : :; ym\Gamma 1ym be the edges, sorted from x0 to x, that are removed from R when X is constructed. (y1y2 is either pq or qr, and y3 2 fp; q; rg.) Suppose the claim is not true. Then there is a smallest index j, 3 ^ j ^ m \Gamma 1, so that one endpoint of yj yj+1, say yj+1, is in j ~rp. Consider the polygon Xj of R that is created by removing the edges y1y2; y3y4; : : : ; yj\Gamma 2yj\Gamma 1 from R. Since yj+1 is the only vertex of Xj that lies in j ~rp, it is visible from p and from r inside Xj. But this means that yj+1x0 intersects fewer edges of R than xx0. This contradicts the choice of x and completes the proof of Claim 1. Claim 2. For each vertex y of X, we have jxyj ! jpqj. Proof (of Claim 2). Clearly, both px and rx are shorter than pq. So let y be any vertex different from p; r; x, and let yy0 be an edge of R that intersects x0x. Because of Claim 1, x is visible within X from p and also from r, so pyxy0 and ryxy0 are convex quadrilaterals. Since y0 lies outside j ~rp, it cannot lie inside both of the circles (p; jprj) and (r; jprj). If y0 lies inside (r; jprj), then jpy0j ? jpxj which implies jyy0j ? jxyj by the 2-Lemma for pyxy0. Otherwise, we have jry0j ? jrxj which implies jyy0j ? jxyj by the 2-Lemma for ryxy0. This concludes the proof of Claim 2 because yy0 is an edge of R and is therefore no longer than pq. Claim 2 and the Fan-Out Lemma imply that all diagonals of Fx(X) are shorter than pq. In the case where pq " rx 6= ;, we now have a contradiction, because the retriangulating process of X eliminates pq and all edges of the resulting new triangulation of R are shorter than pq. In the case where rq " px 6= ;, the new triangulation still includes pq. We show below that the height of the new triangle incident to pq is smaller than the height of pqr, and thus arrive at a contradiction. So assume rq " px 6= ;; in this case pq is an edge of the boundary of X and p is visible from x. If q is also visible from x, then the new triangle incident to pq is pqx with height jxx0j, where x0 2 pq minimizes the distance to x. Analogously, define r0 2 pq that minimizes the 72 distance to r. Since jprj ? jpxj, we have jrr0j ? jxr0j by the 2-Lemma for prxr0. Together with jxr0j * jxx0j, this implies jrr0j ? jxx0j. If q is not visible from x, then pq belongs to the pocket Xuv defined by a cut-off edge uv. We have u = p, w = q, and the center v of Xuv lies in the closure of pqx. So again, either pqv is a triangle, and its height is less than that of pqx and therefore that of pqr, or q is not visible from v, in which case the argument can be repeated. Eventually, we arrive at a triangle incident to pq whose height is less than that of pqr. Two remarks are in order. First, the expandable 2-edge mentioned in the lemma is clearly the shortest among all expandable 2-edges. Second, the assertion of the Lemma is false without the condition that no two diagonals or edges of the complete rng-polygon R are equally long. To see this, take, for example, two equilateral triangles abc and abd and move d slightly towards the common edge ab. For S = fa; b; c; dg, we have rng(S) = fac; cb; bd; dag, ab is a 1-edge, and cd is a 2-edge. So acbd is a complete rng-polygon. There is only one min-max length triangulation of acbd, namely, the one with diagonal ab. But ab is not a 2-edge. 5.6.3 Searching for the Right 2-Edge Two results are needed to show that the 2-edge pq computed by step 3 in Section 5.6.1 is indeed the shortest expandable 2-edge. First note that there are no expandable 2-edges shorter than pq. This is because all 2-edges shorter than pq fail the test of step 3, which are thus not expandable as implied by the following topological lemma. Crossing Lemma. Let v1; v2; : : : ; vn be the sequence of vertices of a simple polygon, and let v1vi and vjvn be two diagonals. Then v1vi " vjvn 6= ; iff j ! i. Proof. The edge vj vn decomposes the polygon into two polygons with vertex sequences v1; v2; : : : ; vj; vn and vj; vj+1; : : : ; vn. If j ! i, then neither of the two polygons has v1 and vi on its boundary. It follows that v1vi crosses from one polygon into the other, and because v1vi is a diagonal, this is only possible by crossing vjvn. To prove the other direction, we assume v1vi " vjvn 6= ; and observe that v1 and vi belong to different polygons because there is no way that v1vi can enter the second polygon and leave it again. Thus, j ! i. 73 We remain to show that the edge pq computed in step 3 is indeed expandable. Expandability Lemma. The shortest 2-edge pq of R that satisfies the conditions of step 3 is also expandable. Proof. We show below that R can be triangulated on both sides of pq using only edges shorter than pq. If we now assume that pq is not expandable, we get a contradiction to the 2-Edge Lemma because pq is the longest edge of the triangulation and all expandable 2-edges are longer than pq. We describe how to triangulate the part of R to the right of ~pq; the other part is symmetric. Case 1: p0 = q00. Assume jqq00j ? jpp0j. Then jqq00j ! jpqj for otherwise p 2 j ~q00q and qq00 would neither be an rng-edge nor a 1-edge with pq on its beneath side. If we apply the triangulation algorithm for incomplete rng-polygons (Section 5.4), once for pp0 and once for qq00, we get a triangulation with the desired properties. Case 2: pp0 " qq00 6= ;. In this case pp0 and qq00 are 1-edges. Because pp0 and qq00 intersect, we have either jp0qj ! jp0pj or jq00pj ! jq00qj from the 2-Lemma for pqp0q00. Assume without loss of generality that jq00pj ! jq00qj. As in case 1 we also have jq00qj ! jpqj, but note that we do not necessarily have jp0pj ! jpqj. We now describe the triangulation process. It takes three steps as illustrated in Figures 5.13 and 5.14. 1. Construct the triangulation Tqq00 of R beyond qq00, using the algorithm for incomplete rng-polygons (see Figure 5.13). 2. Find the subset V of vertices of R, excluding q, that lie in the closure of pqq00, and compute ch(V ). Add the edges of ch(V ) that are diagonals of R to the triangulation, and connect q to all vertices of ch(V ) (see Figure 5.13). 3. Step 2 created untriangulated pockets Yuv , one for each edge uv of ch(V ) that is a diagonal of R. Assume that u precedes v on the clockwise path from p to q00 on the boundary of ch(V ). The pocket Yuv is triangulated as follows. 74 p q q00 p0 ffl ffl ffl ffl ffl ffl Figure 5.13: The shaded portion represents the triangulation beyond qq00; it forms part of the final triangulation. 3.1 Set uL := v if uv is a 1-edge and pq lies on the beneath side of uv. Otherwise, find a vertex uL so that juuLj ! jpqj, uuL is a 1-edge, pq lies beneath uuL, and uuL does not intersect ch(V ). (The existence of such a vertex uL will be established shortly.) 3.2 Construct the triangulation TuuL of R beyond uuL, again using the algorithm for incomplete rng-polygons, but retain only those triangles that lie completely inside the pocket Yuv. Let Xuv denote the untriangulated part of Yuv. 3.3 Construct the fan-out triangulation Fv(Xuv). p=u1 q q00=uK p0=um u=uIuiu j=ui+1 v=uJ ukuL ffl ffl ffl ffl ffl ffl fflffl fflffl ffl Figure 5.14: The shaded portion of the pocket Yuv represents the part of the triangulation TuuL beyond uuL that is retained for the final triangulation. The remaining portion is triangulated by fanning out from v. The remainder of the proof establishes that all diagonals of the thus constructed triangulation are shorter than pq. This is indeed obvious for Tqq00, as constructed in step 1. We now prove an easy extension of the \Delta -Lemma, which implies that all edges created in step 2 are shorter than pq. Claim 1. Let d; e be two points in the closure of triangle abc. Then jdej ! maxfjabj; jacj; jbcjg. 75 Proof (of Claim 1). Assume without loss of generality that e lies in the closure of abd. The \Delta -Lemma for abd implies jdej ! maxfjadj; jbdjg, and the same lemma for abc implies maxfjadj; jbdjg ! maxfjabj; jacj; jbcjg. This completes the proof of Claim 1. If uuL = uv, then juuLj ! jpqj, which implies that all edges of TuuL constructed in step 3.2 are shorter than pq. In this case the proof is complete as Xuv = ; and no edges are added to Yuv in step 3.3. For the remainder of the proof, we thus assume that uL 6= v which is the case only if j ~uv contains at least one vertex of R. We show that a vertex uL satisfying the conditions of step 3.1 indeed exists, and that all edges of the fan-out triangulation Fv(Xuv) are shorter than pq. Assume the sequence of vertices of the part of R beyond pp0 is p = u1; u2; : : : ; q00 = uK ; : : : ; um = p0 (see Figure 5.14). Claim 2. There exists a 1-edge uuL that satisfies the conditions of step 3.1. Proof (of Claim 2). Construct a triangulation Tpp0 of R beyond pp0 using the algorithm for incomplete rng-polygons. This triangulation contains at least one edge uul disjoint from ch(V ). The main invariant of the algorithm (described in Section 5.4) implies that uul is a 1-edge and pq lies on its beneath side. If juulj ! jpqj, then ul satisfies the conditions for uL and we are done. So assume juulj ? jpqj. Similar to the Containment Lemma, we can show that the part of j ~uv to the left of ~uul is contained in j ~uul and thus contains no vertex of R. It follows that the vertices in j ~uv must be among uK+1; uK+2; : : : ; ul\Gamma 1. By the Visibility Lemma, at least one of these vertices is visible from u. Let U be the subset of vertices that are visible from u (including the ones outside j ~uv), and let uL 2 U minimize the distance to u. We have juuLj ! juvj ! juulj and, as above, the part of j ~uuL to the left of ~uul is contained in j ~uul. Therefore, this part contains no vertex of R. The part of j ~uuL to the right of ~uul contains no vertex of R by the choice of uL. It follows that uuL is a diagonal that satisfies the conditions of step 3.1, which completes the proof of Claim 2. We now show two easy facts about TuuL before examining the edges constructed by step 3.3. Claim 3. If uiujuk, with i ! j ! k, is a triangle of TuuL , then uiuk is its longest edge. 76 Proof (of Claim 3). The first triangle constructed is uI uluL, for some I ! l ! L, and its longest edge is uI uL because ul 2 *uIuL . The general assertion follows by induction, which completes the proof of Claim 3. Claim 4. The edges of TuuL that intersect uv, sorted from u to v, are monotonely decreasing in length. Proof (of Claim 4). If uiuj uk, with i ! j ! k, intersects uv, u = uI and v = uJ , then either I ^ i ! j = i + 1 ^ J ! k or I ! i ! J ^ j ! k (see Figure 5.14). In both cases, uiuk intersects uv closer to u than the other intersecting edge, ujuk or uiuj . By Claim 3, uiuk is longer than both, which implies the assertion. Note that if we delete edges from TuuL that intersect uv, then we get a polygon, say Wuv, of which Xuv is the part on one side of uv. We can thus interpret uv as a generator of TuuL restricted to Wuv. Since the edges of Xuv and TuuL are shorter than jpqj, we just need to show that all vertices of Xuv are closer to v than jpqj, and the rest follows from the Fan-Out Corollary. Indeed, we prove a stronger bound on the maximum distance from v to a vertex of Xuv. Claim 5. For each vertex x of Xuv we have jvxj ^ jvuj. Proof (of Claim 5). Consider the vertices of Xuv in turn from u = uI to v = uJ , and assume inductively that jvuij ^ jvuj, for all I ^ i ! j. Consider uj and the triangle uj\Gamma 1ujuk in TuuL . By Claim 4, we have juj\Gamma 1ukj ? jujukj. If uj\Gamma 1ujvuk is a convex quadrilateral, then the 2- Lemma implies jvuj\Gamma 1j ? jvujj, as desired. Otherwise, uj is contained in the closure of vukuj\Gamma 1 and therefore also in the closure of vuuj\Gamma 1. The \Delta -Lemma implies jvujj ! maxfjvuj; jvuj\Gamma 1jg, which completes the proof of Claim 5. This also completes the proof of the lemma. The following theorem summarizes the algorithmic implication of the above. Min-Max Length Theorem. A min-max length triangulation of a set of n points in R2 can be constructed in quadratic time and storage. 77 5.7 Undoing the Simulated Perturbation In general, for every point set S in R2, there is an arbitrarily small perturbation S0 so that S0 satisfies convenient non-degeneracy assumptions (see [EdM"u90]). For a point p 2 S, we denote its perturbed version by p0. In our algorithm, this means that no two pairs of points in S0 define the same distance. Furthermore, the non-degenerate properties of S are maintained, that is, for four not necessarily distinct points p; q; r; s 2 S with jpqj ! jrsj, we have jp0q0j ! jr0s0j. Let us consider the effects of the perturbation on the computation of a min-max length triangulation. First, if p0q0 2 rng(S0), then pq 2 rng(S), but not vice versa. In other words, we may have fewer edges in the perturbed setting. This, however, does not adversely influence the algorithm since rng(S0) is still connected and spans S0. Second, when the edges of ch(S0) are added and the polygonal regions defined by ch(S0) [ rng(S0) are triangulated, it can happen that triangles a0b0c0 are constructed whose unperturbed counterparts abc are flat, that is, a; b; c are collinear. Although this is not a problem for the algorithm, it is somewhat distressing when this triangulation is interpreted as a triangulation of S. The remainder of this section shows how to remedy this deficiency. Let T (S0) be a min-max length triangulation of S0, and consider its unperturbed version T (S), that is, pq 2 T (S) iff p0q0 2 T (S0). A longest edge of T (S) is no longer than a longest edge of any min-max length triangulation mlt(S) of S, since mlt(S0), the perturbed version of mlt(S), is a valid triangulation of S0 and would otherwise contradict that T (S0) is a minmax length triangulation of S0. The reverse is also true, namely, a longest edge of T (S) is no shorter than a longest edge of mlt(S). We show this by converting T (S) into a min-max length triangulation of S. Consider the dual graph T \Lambda (S0) of T (S0) and call a node a0b0c0 flat if a; b; c; are collinear. Determine the connected components of the subgraph of T \Lambda (S0) induced by the set of all flat nodes. Each component corresponds to a collection of collinear points in S, interconnected by flat triangles; see Figure 5.15. Carry out the following steps for one component at a time. Remove all edges of the flat triangles of the component, sort the corresponding points along the supporting line, and add edges connecting points that are adjacent in the sorted order. This produces regions bounded by more than three edges, as shown in Figure 5.15. All vertices 78 ffl ffl ffl ffl fflffl ffl fflffl ffl ffl ffl ffl fflffl ffl fflffl Figure 5.15: The five points in the middle of the left triangulation are the perturbed versions of five collinear points in the right triangulation. x of such a region are collinear, except for one vertex y, which is connected to the first and last of the vertices x. Triangulate this region by connecting y to all other vertices x. By the \Delta -Lemma, the newly introduced edges are no longer than the longer of the two original edges incident to y. 5.8 Extension to Normed Metrics A convex region D ` R2 which is symmetric with respect to the origin can be used to impose a norm on R2: for a point x 2 R2, define kxk = kxkD = ff if x lies on the boundary of ffD = fffy 2 R2 : y 2 Dg. The norm can then be used to impose a (normed ) metric on R2: for two points x; y 2 R2, define jxyj = jxyjD = ky \Gamma xkD. D is the unit-disk of the metric and the boundary of D is its unit-circle. Notice that the three requirements for a metric are indeed satisfied. First, jabj = 0 iff a = b because kxk = 0 iff x is the origin. Second, jabj = jbaj because D is centrally symmetric and therefore kxk = k\Gamma xk. Third, the triangle inequality, jacj ^ jabj + jbcj, follows from the convexity of D. Examples of normed metrics are the lp-metrics, for p = 1; 2; 3; : : :, and the so-called A-metric discussed in [WWW85] for its applications to VLSI. In this section, we assume that the triangle inequality is strict unless a; b; c lie on a line in this order. This is the case iff the defining convex region D is strictly convex, that is, no line intersects the boundary of D in more than two points. This assumption is convenient and in fact without loss of generality as every convex but not strictly convex region D0 can be approximated arbitrarily closely by a strictly convex region D. Computationally, this approximation can be 79 simulated by defining kxkD = kxkD0 + "kxk2; where kxk2 is the Euclidean or l2-norm and " is an arbitrarily small but positive real number. Clearly, if " is sufficiently small, then a min-max length triangulation under D is also a min-max length triangulation under D0. In the remainder of this section, we point out where the developments in Sections 5.1 through 5.6 need to be adjusted when the Euclidean metric is replaced by an arbitrary normed metric. Most importantly, the graphs defined in Section 2.4 can be extended in a natural way. If we now stipulate that "circle" means a homothetic copy of the unit-circle as defined above and "jabj" means the distance under the normed metric defined by D, then the definitions of mlt(S), D(S), rng(S), and mst(S) can be taken verbatim. The minimum spanning tree, mst(S), is connected and spans S, and the Delaunay triangulation, D(S), is plane because any two circles intersect in at most two points. Since we still have mst(S) ` rng(S) ` D(S), we conclude that all three graphs are connected and plane and they span S. We remark that these three graphs are not necessarily plane if D is not strictly convex. The developments in Sections 5.1 through 5.6 are all based on a small number of basic facts, namely, the distance relations expressed by the 2-Lemma and the \Delta -Lemma, the convexity of the lune of an edge, and the straightness of the bisector of two points. The 2-Lemma and the \Delta -Lemma are direct consequences of the triangle inequality and hold in the stated form (with strict inequality) for arbitrary normed metrics as long as D is strictly convex. The lune of two points is clearly convex as it is the intersection of two homothetic copies of D. Unfortunately, the bisector of two points p 6= q, `pq = fx : jxpj = jxqjg, is not necessarily straight. Nevertheless, `pq is still a simple curve that divides R2 into two unbounded regions, called half-planes, one containing p and the other q. The two half-planes are star-shaped with respect to p and q, that is, any line through p or q intersects `pq in at most one point. In addition, `pq is symmetric with respect to p+q2 because D is centrally symmetric. There is only one place where the straightness of the bisector is used in a substantial way, and that is in the proof of Fact 5.3. We restate this fact and show how to prove it without the 80 use of the straightness of the bisector. Recall that bd (b0d0) is said to be switchable if ac (a0c0) is no longer than the longest edge of the triangulation T . Fact 5.3. It is not possible that both bd and b0d0 are non-switchable. Proof. As established in Fact 5.2, if bd is non-switchable, then a and d are contained in the half-plane defined by `pq that contains q. Symmetrically, if b0d0 is not switchable, then a0 and d0 are contained in the other half-plane. Unlike in the Euclidean case, it is possible that ad and a0d0 intersect `pq. It is thus possible that ad precedes a0d0 in the order of edges sorted from p to q by their intersections with pq, as in Figure 5.16. Below we argue that if this is the case, then ad (and symmetrically a0d0) is switchable. In particular, we show jadj ? japj which, together with japj * jacj from Fact 5.2, implies that ad is switchable. ffl ffl ffl ffl ffl ffl p q a d a0 d0 Figure 5.16: Although a and d lie on q's side of the bisector and a0 and d0 lie on p's side, ad intersects pq closer to p than a0d0 does. This is not possible if the bisector is a line as for the Euclidean metric; see Figure 5.6. One characteristic of the described situation is that ad intersects `pq in at least one point inside the lune of pq. Let x be such an intersection point closest to a. If pq " dx 6= ;, then pdqx is a convex quadrilateral with jpdj * jpqj by construction. The 2-Lemma thus implies jdxj ? jqxj = jpxj. It follows that jadj = jaxj + jdxj ? jaxj + jpxj ? japj. On the other hand, if pq " dx = ;, then consider the point y = ad " pq and note that jpyj ^ jqyj. We derive jdyj ? jpyj from jpyj + jdyj ? jpdj * jpqj * 2jpyj. Therefore, jadj = jayj + jdyj ? jayj + jpyj ? japj as desired. 81 All other steps of the proof of the Subgraph Theorem go through unchanged for arbitrary normed metrics. We thus get the following generalization. General Subgraph Theorem. Let S be a point set in R2 equipped with a normed metric with strictly convex unit-disk. Then S has a min-max length triangulation mlt(S) so that rng(S) ` mlt(S). So the algorithm for computing a min-max length triangulation is clear--it is the same as for the Euclidean metric, only that the length of edges is now measured in terms of a normed metric. We assume that the length of an edge in this metric can be computed in constant time. A careful reexamination of Sections 5.3 through 5.6 shows that the specialized polygon triangulation algorithm works also in the context of arbitrary normed metrics. We remark, however, that it includes the distance computation between a point and a line segment. Although it is certainly reasonable to assume that this can be done in constant time too, the observation in the remark at the end of Section 5.4 can be used to avoid this computation. We thus have the following algorithmic result which generalizes the Min-Max Length Theorem. General Min-Max Length Theorem. Let S be a set of n points in R2 equipped with a normed metric with strictly convex unit-disk. Given the relative neighborhood graph, a minmax length triangulation of S can be constructed in time O(n2). As mentioned above, a norm with non-strictly convex unit-disk can be simulated by one with strictly convex unit-disk. It follows that the quadratic time bound also holds for arbitrary normed metrics. The result stated in the General Min-Max Length Theorem raises the question of how fast rng(S) can be constructed. The trivial algorithm tests all \Gamma n2\Delta edges, each in time O(n), and therefore takes time O(n3). Faster algorithms are known for the lp-metrics where O(n log n) time suffices [JKY92, Kata88, Lee85]. 5.9 Discussion The main contribution of this chapter is the first polynomial time algorithm for computing a min-max length triangulation of a set S of n points in R2. The components of the algorithm are described in Sections 5.1, 5.4, and 5.6.1. Given the relative neighborhood graph of S, the 82 algorithm takes time O(n2). The algorithm works for arbitrary normed metrics. The polynomial time bound follows because the relative neighborhood graph of S can be found in polynomial time. The same problem formulated for general plane geometric graphs can also be solved in polynomial time provided the minimization condition is defined over all edges including the constraining ones. This follows immediately from a constrained version of the Subgraph Theorem. In the Euclidean metric case, the problem can actually be solved in quadratic time because the relative neighborhood graph with constraining edges can be computed in O(n log n) time [SuCh91]. The question remains whether or not a min-max length triangulation, with or without constraining edges, can be computed in less than quadratic time. The approach used by the solution is a version of the subgraph approach mentioned in Section 2.5. Both Plaisted and Hong [PlHo87] and Lingas [Ling87] used this approach to compute approximations of the minimum length triangulation. It is interesting to see whether it can also be useful to other criteria. In our case, the technique of retriangulation plays an important role in the developments, and this will probably be the case also in other applications of the subgraph approach1. The results of this chapter are an out-growth of our general efforts to understand triangulations that optimize length criteria. Currently, min-max length is the only non-trivial one known to be computable in polynomial time. There are many related problems whose complexities remain open; see Section 1.3.2. In particular, the natural extension of the min-max length criterion to its vector form is not solved--it is no longer true that there is always an optimal triangulation that contains the relative neighborhood graph as a subgraph. The smallest example that illustrates this observation consists of four points a; b; c; d so that c and d lie fairly close to b, ab and cd intersect, and c and d both lie outside the circle with radius jabj and center at a. 1Incidentally, retriangulation is also the main idea in proving the correctness of the edge-insertion paradigm. 83 Acknowledgments The results in this chapter are jointly developed by Herbert Edelsbrunner and myself [EdTa91]. We thank Jerzy Jaromczyk (University of Kentucky) for pointing out various references on relative neighborhood graph, in particular, the paper by Su and Chang [SuCh91] that implies a quadratic time algorithm for the constrained min-max length triangulation problem in the Euclidean case. 84 Chapter 6 Conforming Delaunay Triangulations A conforming Delaunay triangulation for a plane geometric graph G = (S; E) is introduced in Section 1.2 as an extension to the Delaunay triangulation for a point set. It is a genuine Delaunay triangulation, or more precisely, a completion of a degenerate Delaunay triangulation. Its relation to G is that each vertex in S is also a vertex of the triangulation, and each edge of E is the union of some edges and vertices of the triangulation [BFL88]. The problem of constructing a conforming Delaunay triangulation for a given plane geometric graph is non-trivial. In particular, it is not clear how many new vertices are really needed to achieve conformity. Previous work [Bois88, NaSr91, Olou91, Saal91, SaPe91] fails to provide polynomial upper bounds on this issue. Such a bound, on the other hand, is given in this chapter. Section 6.1 formalizes the problem and presents some preliminary results. Section 6.2 gives the first polynomial upper bound on the number of vertices necessary for a conforming Delaunay triangulation. Section 6.3 explicitly formulates the algorithm implicit in the proof of the upper bound. Lastly, Section 6.4 summarizes this chapter and mentions some open problems. 85 6.1 Preliminaries Let G = (S; E) be a plane geometric graph. A completion, C, of a Delaunay triangulation conforms to G if every vertex of G is a vertex of C and every edge of G is the union of edges and vertices of C. The problem is to find a small point set V so that D(V ) has a completion that conforms to G. We call such a completion a conforming Delaunay triangulation of G. It is also desirable to have an algorithm that constructs V as well as a completion of D(V ) that conforms to G. The next lemma shows that the latter task can be handled by existing constrained Delaunay triangulation algorithms [Chew89, Seid88], once we have an algorithm that finds V . Thus, we can focus on the process of finding V . As mentioned before, each edge ab of a completion of D(V ) satisfies the empty disk property, that is, there exists a circle through a and b so that no point of V belongs to the disk bounded by the circle. We now argue that this property is also sufficient for the existence of a conforming Delaunay triangulation. Call the portion of an edge of G between two contiguous points of V (but excluding them) on this edge an interval. Lemma 6.1 D(V ) has a completion that conforms to G iff every interval defined by G and V has the empty disk property with respect to V . Proof. The only if part follows from the definition of a completion of D(V ). For the if part, we assume that every interval ab has the empty disk property. If ab is an edge of D(V ) then nothing has to be proved. Otherwise, no edge of D(V ) can intersect ab because the closure of the disk bounded by any circle passing through the endpoints of such an edge contains a or b or both. Also, there is no other interval that intersects ab because G is plane. So ab, and all other intervals that are not edges of D(V ), can be added to D(V ) without introducing any intersection. We can add zero or more non-intersecting edges arbitrarily until a completion of D(V ) is obtained. A Lower Bound. An edge ab 2 E that belongs to the boundary of the convex hull of S automatically satisfies the empty disk property, and no points on ab need to be introduced. For other edges ab, there are points on both sides of the line through ab. It is thus possible that ab 86 does not satisfy the empty disk property, in which case points must be added to subdivide ab into smaller intervals. In some cases, the size of V must be at least quadratic in the size of G. This bound can be shown using the example of Figure 6.1 which consists of m = jEj edges and n = jSj = 2m + 2k vertices. The edges are parallel and very close to each other. The isolated vertices come in k fflfflfflffl fflffl fflfflfflffl fflfflffl ffl ffl ffl ffl ffl Figure 6.1: An \Omega (mn) lower bound example on the number of vertices of a conforming Delaunay triangulation. In the example shown, m = 6, k = 3, and therefore n = 2m + 2k = 18. pairs, with one vertex on each side of the group of edges. Provided the edges are sufficiently close to each other, and the vertices are sufficiently close to the edges, it will be necessary to place a point approximately between the two vertices of every pair on every edge. This proves that at least mk points need to be added to obtain a conforming Delaunay triangulation. The lower bound of \Omega (mn) follows for k = \Omega (n). For smaller k, the endpoints of half of the m edges can be used to play the role of the isolated vertices. Prior Work. A common approach to produce a conforming Delaunay triangulation is to place sufficiently many points on the edges of the plane geometric graph so that each interval has a circle that avoids all other edges [Bois88, NaSr91, Olou91, Saal91, SaPe91]. This can always be achieved except maybe at places close to shared endpoints where sharp angles are formed. This special case is handled by placing points at the intersections of the edges with a sufficiently small circle drawn around the common endpoint. The method avoids the need for backtracking as no point placed on any edge harms any interval that already has such a circle. The price, however, is a possibly horrendous number of new points. Indeed, there is no function f (n) that can bound the number of points although for every problem instance it is finite. In particular, the number of points added grows as the edges move closer to each other. An Exponential Upper Bound. An upper bound that depends solely on n can be obtained as follows. Initially, set V := S and consider all m edges as unprotected. Treat the edges of G in 87 turn. At the time the ith edge is treated, it may consist of various protected and unprotected intervals. Place sufficiently many points on the unprotected intervals so that each new interval has a circle that does not enclose any point of the current set V . Each such circle may, however, intersect other edges. To prevent points from being placed inside the circle later in the process, we place points at the intersections between the circle and any unprotected interval of another edge. Declare each new interval as protected if it is enclosed by the circle and unprotected otherwise. See Figure 6.2. ffl ffl ffl ffl ffl ffl ffl ffl ffl ffl 0 1 2 3 4 5 6 7 8 9 ffl fflffl ffl ffl ffl fflffl ffl ffl Figure 6.2: The original graph, G, has vertices 0 through 9 and edges 01, 23, 45, 67 and 68. First, edge 01 is treated. In the process, two new points are added to 01. The resulting three circles intersect the other edges in seven points, which are also added. Each edge of G consists now of protected and unprotected intervals. The number of points needed to treat the ith edge does not exceed the current size of V since it suffices to project the current set V orthogonally onto the ith edge. Similarly, the number of circles needed for the ith edge does not exceed the current size of V . Assume inductively that jV j ^ n(2m + 1)i\Gamma 1 before the next step that treats the ith edge. The next step creates at most n(2m + 1)i\Gamma 1 circles intersecting the remaining edges in at most 2m points each. The size of V thus increases to at most n(2m + 1)i\Gamma 1 + n(2m + 1)i\Gamma 12m = n(2m + 1)i. The total number of points at the end of the process is therefore at most n(2m + 1)m. This method apparently produces far too many points. An improvement was found by Mehlhorn, Sharir, and Welzl. Their method combines the projection of points with a divideand-conquer scheme and achieves a subexponential although not yet polynomial bound. The idea of protected and unprotected intervals turns out to be valuable in our effort to obtain a polynomial upper bound on the number of points. 88 6.2 The Upper Bound Given a plane geometric graph G = (S; E), with jSj = n and jEj = m, this section shows how to find O(m2n) points so that each resulting interval has the empty disk property. As defined earlier, an interval is the portion of an edge between two contiguous points of V chosen on this edge. If no point of an edge belongs to V , then this edge itself is an interval. 6.2.1 The Global Idea The point set V is constructed in two steps, the blocking and the propagation phase. Initially, V contains only the vertices of G, that is, V := S. The goal of the blocking phase is to find O(n) pairwise disjoint disks that contain no points of S so that the union of their closures is connected and contains S. Each circle bounding such a disk is called a blocking circle. After finding these disks, we add the intersections between blocking circles and edges of G to the set V . In addition, we add the O(n) points at which blocking circles touch each other. The new set V forms the vertex set W of a plane geometric graph H which conforms to G. The edges of H are the intervals of G together with edges connecting contiguous points of V on blocking circles. H has two types of edges. Each protected edge is enclosed by a blocking circle; its endpoints lie on the blocking circle. All other edges are unprotected. By construction, protected edges have the empty disk property with respect to the current set V . We will make sure that no points inside the blocking circles are later added to V so that this property persists with respect to all future sets V . The unprotected edges are further subdivided into intervals in the propagation phase. For an edge or interval ab, we define the minidisk of ab, denoted by Mab, as the smallest disk containing ab. In other words, Mab is the disk bounded by the circle with ab as a diameter. If ab is unprotected and its minidisk contains a point c 2 V visible from every point of ab then a point c0 subdividing ab into ac0 and c0b is added to V . This point c0 will be chosen so that c lies outside Mac0 and Mc0b. 89 6.2.2 The Details The Blocking Phase. We show how to use a minimum spanning tree of S to construct n \Gamma 1 disks D1; D2; : : : ; Dn\Gamma 1 that satisfy the following properties: (1) Di " S = ; for all 1 ^ i ^ n \Gamma 1, (2) Di " Dj = ; for all 1 ^ i ! j ^ n \Gamma 1, (3) D = n\Gamma 1[ i=1 (closure of Di) is connected, and (4) S ` D. Recall that a minimum spanning tree of S, mst(S), is a spanning tree of the complete graph (S; \Gamma S2\Delta ) whose sum of edge lengths is a minimum (Section 2.4). An important property of mst(S) is that the minidisk of every edge of mst(S) is disjoint from S. Label the vertices of mst(S) from 0 through n \Gamma 1 so that for every 0 ^ j ^ n \Gamma 1 the vertices 0; 1; : : :; j induce a subtree of mst(S). Define ij so that ijj is an edge of this subtree. Notice that ij ! j and that ij is unique. The edges ijj are now used to define the disks Dj. The disk D1 is the minidisk of edge 01. The disk Dj, for 2 ^ j ^ n \Gamma 1, is maximal so that (i) its center lies on ijj, (ii) its bounding circle goes through j, and (iii) it is disjoint from disks D1 through Dj\Gamma 1 constructed earlier. Clearly, Dj ` Mijj . This implies property (1). Properties (2), (3), and (4) follow from the construction. Let S0 be the set of points where the blocking circles intersect the edges of G, and let S00 be the set of points (not in S0) where the blocking circles touch each other. As described above, the points in S0 and S00 are added to V . Let W be the new set V , and let H = (W; F ) be a plane geometric graph with F = F 0 [ F 00 defined as follows. The set F 0 contains all intervals on edges of G. Remember that by construction all points of W lie on the n \Gamma 1 blocking circles. 90 Consider a disk Di bounded by a blocking circle Ci, and let p0; p1; : : : ; pk\Gamma 1; pk = p0 be the points of W that lie on Ci in this sequence. These points define a convex k-gon with edges p`p`+1, 0 ^ ` ^ k \Gamma 1, termed walls. Some of these walls may be intervals on edges of G and therefore belong to F 0. In any case, F 00 is the collection of all walls. This completes the definition of H which conforms to G; see Figure 6.3. ffl ffl ffl ffl ffl ffl ffl ffl 0 1 2 3 4 5 6 7 ffl ffl ffl ffl ffl ffl ffl ffl ffl Figure 6.3: The original graph, G, has vertices 0 through 7 and edges 17, 23, 46 and 67. The edges of the minimum spanning tree, 01, 12, 23, 14, 45, 56 and 57, are indicated by broken lines. Each edge of the tree corresponds to a blocking circle. Each blocking circle encloses protected edges of H. Note that each wall is protected by a blocking circle. The collection of walls defines another plane geometric graph, I = (W; F 00). Clearly, I is a subgraph of H. Note that all faces of H, excluding the unbounded face, are simply connected because H is connected. For convenience, we shall adopt the topology of the sphere in our discussion so that all faces of H are simply connected. Similarly, all faces of I are simply connected because I is connected. The Propagation Phase. The unprotected edges of H are further subdivided into intervals during a non-deterministic process. Initially, every unprotected edge is also an unprotected interval. Consider an unprotected interval ab and its minidisk Mab. Call a point c 2 V visible from ab if the interior of abc is disjoint from all edges of H. Suppose a point c 2 V visible from ab is contained in Mab. We add c0 to V , where c0 is the orthogonal projection of c onto ab, and thus subdivide ab into ac0 and c0b. Repeat this step until there is no unprotected interval ab with such a point c. This completes the description of how the point set V is constructed. 91 6.2.3 The Analysis This subsection shows that the eventual size of V is O(m2n). The blocking phase adds at most (2m \Gamma 1)(n \Gamma 1) intersection points between edges and circles and fewer than 3n points where circles touch each other. The latter bound follows from the planarity of the intersection graph of the blocking circles. We now focus on proving that each point created in the blocking phase gives rise to at most O(m) points in the propagation phase. We begin by proving a few properties of the propagation phrase. Let ab be an unprotected interval at some point in time during the process, and let c 2 V lie in Mab. Then the orthogonal projection c0 of c onto the line through ab lies strictly between a and b, i.e., c0 2 ab. Furthermore, c 62 Mac0 and also c 62 Mc0b. Assume now that c 6= x; y is a point on some edge xy of G. All points in V \Gamma (S [ S00) are of this form. Then we have the following fact. Lemma 6.2 There are at most two intervals, ab and a0b0, so that c is visible from both and contained in their minidisks. Furthermore, ab and a0b0 lie on different sides of the line through xy. Proof. If c 2 Mab then "acb ? ss2 , and if c is visible from ab then a and b lie on the same side of the line through xy. The same is true for a0b0. So if ab and a0b0 lie on the same side of the line then one endpoint of a0b0 must lie between a and b as seen from c. This contradicts the assumption that c is visible from ab and from a0b0. Next, let c 2 Mab be visible from ab, and c0 be the orthogonal projection of c onto ab. Then we have the following fact. Lemma 6.3 There is no interval a00b00 on the same side of the line through ab as c so that c0 is visible from a00b00 and c0 2 Ma00b00. Proof. Assume such an a00b00 exists. Then "a00c0b00 ? ss2 which implies that c lies between a00 and b00 as seen from c0. This either contradicts that c is visible from ab or that c0 is visible from a00b00. 92 Assume now that c 2 V does not lie on an edge of G, so c 2 S [ S00. Similar to Lemma 6.2, we have the following fact as there can be at most three angles larger than ss2 packed around c. Lemma 6.4 There are at most three intervals ab so that c is visible from ab and c 2 Mab. A Locality Property. Notice that the propagation phase takes care only of local constraints. In other words, it considers only visible point-interval pairs c; ab. Although the minidisk of ab can contain other points of V , it is indeed justified to ignore such points, as we will see shortly. Let ab be an unprotected interval. We call the minidisk Mab locally empty if it contains no point of V that is visible from ab. Furthermore, Mab is empty if it contains no point of V at all. To prepare for the next lemma, we consider an interval ab and a point c 2 Mab. If c is not visible from ab then there are intervals st that intersect abc. We say that st separates c from ab if both endpoints, s and t, lie outside Mab. Otherwise, st hinders the visibility between c and ab but it does not separate. Let Ec;ab be the set of intervals that separate c and ab, and define Fc;ab as the set of (non-separating) intervals that hinder the visibility between c and ab. It is interesting to observe that Fc;ab = ; or there is another point d of V in Mab with Ed;ab ` Ec;ab and Fd;ab = ;. To see this, choose a point x in the interior of abc so that the interior of abx does not intersect any edge of H. Move x continuously and straight towards c until either a side of abx hits a vertex d or x hits a non-separating interval uv of H. In the second case at least one of the two endpoints, say u, lies in Mab. Slide x on uv towards u until either a side of abx hits another vertex d or x reaches u (then d = u), whichever happens first. The path of x crosses only intervals that separate c and ab, therefore Ed;ab ` Ec;ab. Lemma 6.5 If the minidisks of all unprotected intervals are locally empty then they are all empty. Proof. Suppose the claim is false. Then, there is an unprotected interval ab whose minidisk Mab contains a point c 2 V . As argued in the preceding paragraph, we can make the extremal assumption that ab and c are chosen so that the number of separating intervals Ec;ab is a global minimum and Fc;ab = ;. Let st be an interval that separates ab from c. Note that st is not 93 protected because every circle through s and t encloses at least one of a, b and c. But if st is an unprotected interval, we have c 2 Mst because s and t are outside Mab. Furthermore, st cuts Mab into two pieces, and the piece that contains c is properly contained in Mst. Therefore Ec;st ` Ec;ab and we have proper containment because st 2 Ec;ab does not belong to Ec;st. This either contradicts the extremal assumption or that st is locally empty. Propagation Sequences. We are now ready to analyze the number of points created in the propagation phase. Our particular goal is to show that each point c created in the blocking phase generates at most 3m points in the propagation phase. We say that a point c generates another point d if there is a sequence c = c0; c1; : : : ; ck = d so that ci+1 is created as the orthogonal projection of ci onto some interval during the propagation phase, for 0 ^ i ^ k \Gamma 1. The sequence c0; c1; : : : ; ck is called a propagation sequence. It is non-trivial if k * 1, and it is maximal if c0 is created in the blocking phase and ck generates no further point. Note that all ci, i * 1, of a maximal propagation sequence lie on unprotected edges of H, and these edges are contained in edges of G. Every point d created in the propagation phase gives rise to at most one point d0. To see this, we first note that such a point d lies on an edge xy of G. Now Lemma 6.2 implies that d is visible from at most two intervals whose minidisks contain d. By Lemma 6.3 and because d itself is generated by an orthogonal projection, d generates another point d0 on at most one of these two intervals. Together with Lemma 6.4, this implies that a point of V constructed before the propagation phase gives rise to at most three non-trivial maximal propagation sequences. In fact, there are at most two such sequences per point not in S [ S00. To establish that the length of a maximal propagation sequence is at most m, it suffices to prove the following. Lemma 6.6 No propagation sequence can have two or more points on the same edge of G. Proof. Suppose the claim is false. Consider a minimal propagation sequence, c = c0; c1; : : : ; ck = d, so that c and d lie on the same edge xy of G. Consider the polygon, P , whose boundary consists of the line segments cd and cici+1, for 0 ^ i ^ k \Gamma 1. Recall that walls are protected, so no points are projected on or across them. Thus, P lies completely within a face of I. Since all vertices of G are also vertices of I, and because all faces of I are simply connected, there can 94 be no vertex of G inside P . Thus, each edge of G that intersects P has its endpoints outside P . It thus intersects the boundary of P in at least two points. Since c0; c1; : : : ; ck is minimal, it follows that k = 2 and that c0 and c2 lie on the same side of the edge xy of G that contains c1. But this contradicts Lemma 6.3. As mentioned earlier, jS [ S00j ! 4n. Each point c 2 S [ S00 gives rise to at most three maximal propagation sequences of length at most m + 1 each. The point c itself is the only point of these sequences that does not necessarily lie on an edge of G. The number of other points created during the blocking phase is less than 2mn. Each such point gives rise to at most two maximal propagation sequences of length at most m each. The total number of points after the propagation phase is thus less than 4n(3m + 1) + 2mn(2m \Gamma 1) = 4m2n + 10mn + 4n: This proves the main result of this section. Theorem 6.7 Let G = (S; E) be a plane geometric graph with jSj = n and jEj = m * 1. There exists a point set V of size jV j = O(m2n) so that its Delaunay triangulation has a completion that conforms to G. 6.3 Implementing the Proof The proof of the O(m2n) upper bound presented in Section 6.2 is constructive and can be translated into an algorithm without much effort. The only demanding step is the implementation of the propagation phase. In order to keep the time-complexity roughly within the same order of magnitude as the number of points added, we need to project the points in a sequence that is computationally inexpensive. We will assume that point coordinates can be stored in constant amount of storage and that basic geometric operations, such as intersecting a circle with an edge and projecting a point onto a line, can be carried out in constant amount of time. As usual, plane geometric graphs are stored using the quad-edge data structure of Guibas and Stolfi (Section 1.2). 95 6.3.1 The Blocking Phase A minimum spanning tree of a set of n points in the plane can be computed in time O(n log n). This requires the construction of the Delaunay triangulation of the points and running a standard minimum spanning tree algorithm on the graph of this triangulation; see, for example, [Edel87, Section 13.2.5]. Alternatively, a minimum spanning tree can be obtained in time O(n2) directly from the complete graph of the points. The slower method is certainly easier to implement. After computing the tree, we need to find the disks D1; D2; : : :; Dn\Gamma 1 that satisfy properties (1) through (4). Most straightforwardly, these disks can be constructed one by one as explained in Section 6.2. For each j, the largest disk Dj needs to be found so that its center lies on ijj, j lies on the bounding circle of Dj, and Dj avoids all Di for i ! j. This can be done in time O(j). The total amount of time for this step is thus O(n2). The plane geometric graphs H and I can be computed by intersecting the bounding circles of the Dj with each other and with the edges of G. The resulting O(mn) intersection points can be computed and sorted along circles and edges in time O(mn log n). 6.3.2 The Propagation Phase Recall that I is a subgraph of H and contains none of its unprotected edges. A point c 2 V is projected onto an interval ab only if ab is unprotected. Thus, projections happen only within faces of I. We can thus restrict our attention to a single face of I. As mentioned earlier, I is connected and therefore its faces are simply connected. Each face of I is further subdivided into regions (of H) by unprotected edges of H. Each region is also simply connected, and can be treated computationally as bounded by a simple polygon defined by oriented edges that have the region on their left (Section 1.2). A Tree of Regions. Consider a face f of I. Let Rf be the graph whose nodes are the regions of f , and whose arcs connect regions that share unprotected edges of H. Each subdividing unprotected edge has both endpoints on the boundary of f , which implies that Rf is a free tree. It will be convenient to fix an arbitrary node as its root and thus impose a parent-child 96 relation on adjacent node pairs. Points will be projected onto unprotected edges in three stages. The first stage computes an initial set of projections that avoids difficult situations in the second stage. The second stage computes and sorts segments along the boundary of each region. The last stage consists of a post-order and a pre-order traversal of Rf . Consider two adjacent nodes * and , of Rf , and let ab be their shared unprotected edge. Points on the boundary of * that are projected onto ab are said to be exported from * to ,. Symmetrically, we say they are imported by ,. The points projected onto ab are stored in two separate sorted lists, L*, and L,* , one for each side of ab. The complete list of points exported from * to ,, L*,, can be computed only after all import lists L^* , for ^ 6= , adjacent to *, are available. Note that the import list from ,, L,* , is not necessary for computing L*, because a propagation sequence follows only one direction of a path in Rf (Lemma 6.6). Stage 1: subdividing unprotected edges. A vertex vj of * is reflex if the angle inside * exceeds ss, i.e., vertices vi; vj; vk form a right turn where ~vivj and ~vjvk are the oriented edges on the boundary of *. The first stage projects every reflex vertex c onto all unprotected edges ab for which there exists a portion a0b0 ` ab so that c is visible from a0b0 and c 2 Ma0b0. Since "a0cb0 ? ss2 there can be at most three such edges ab. As a precaution, we do not require that c be visible from ab. This way c does not need to be reconsidered after ab gets subdivided. Although such projections are not prescribed by the proof in Section 6.2, they neither invalidate the correctness nor the analysis of the construction. Each reflex vertex is necessarily a vertex in S [ S00, so there are fewer than 4n of them. Since each vertex is projected at most three times, we thus increase the number of unprotected edges by less than 12n. Here is how we find the at most three unprotected edges for a reflex vertex c. The parts of the boundary of * visible from c can be computed in a single walk along the boundary of *; see, for example, [ElAv81, Lee83, JoSi87]. The amount of time needed for the walk is proportional to the number of edges. Select the at most three edges that have connected portions visible from c along an angle exceeding ss2 . Project c orthogonally onto these at most three edges. Each projection subdivides an unprotected edge into two such edges. The rest of the algorithm uses the subdivision of H produced in stage 1. It will therefore be convenient to call the elements of this subdivision vertices and edges. After the completion 97 of stage 1, no reflex vertex visible from an unprotected edge ab lies inside the minidisk Mab. It thus follows that if a point c lies in Mab and is visible from a point on ab then it is also visible from ab. Stage 2: computing boundary segments. This stage is a preprocessing step that speeds up computations in stage 3. It prepares the boundary of * in such a way that points can be projected onto various unprotected edges in a single walk along the boundary of *. To this end, we associate pieces of the boundary, called segments, with the unprotected edges of *. A segment for an unprotected edge ab is a maximal connected piece of *'s boundary so that every point x of the segment is visible from ab and contained in Mab. Note that segments do not include their endpoints. Since * is simply connected, a point x is visible from ab iff it is visible from a and also from b. The segments of ab are constructed as follows. 1. Find the part of *'s boundary visible from a. As mentioned above, this can be done in a single walk along the boundary. 2. Find the part of *'s boundary that is also visible from b. Again a single walk suffices. 3. Intersect the identified boundary pieces with Mab. Define the rank of *, r(*), equal to the number of unprotected edges of *, and let j*j be the total number of edges of *. If an edge bounds * on both sides, that is, the edge belongs to the interior of the closure of *, then it is counted twice. By construction, this can be the case only for protected edges. After carrying out 1 through 3 for each unprotected edge of *, we obtain a collection of segments. Because of Lemma 6.2, the segments along the boundary of * are pairwise disjoint. In other words, the segments form a sequence, and they can be sorted in time proportional to j*j plus their number. This is because along an edge of * the segments are ordered consistently with the order of their corresponding unprotected edges. We will see later that the number of segments is less than 2 r(*) + j*j. Stage 3: traversing the tree. In a post-order traversal, the children ^ of a node * are visited before *. Visiting a node * in this case means computing the export list to its parent ,. Notice that because of stage 1, * and , may share several unprotected edges. Still, their union is the original unprotected edge of * and ,, and L*, can be obtained by concatenating the lists 98 obtained by projecting points onto these unprotected edges. We can assume that at the time the export list of * to , is computed, all import lists L^* are available. List L*, is constructed in a single walk along the boundary of *. Whenever a segment that belongs to an unprotected edge shared by * and , is encountered, the points on this segment are projected orthogonally onto the unprotected edge. These points can be vertices of * or points in import lists of *. The result is the list L*,. It is automatically sorted if we process the points in their order along the boundary of *. After the post-order traversal of Rf , all child-to-parent lists are complete. In order to compute the export lists of a node * to its children ^, we need to first construct the import list from its parent, L,*. This is done in a pre-order traversal of Rf . A node is visited before its children, and visiting a node * now means computing all export lists L*^. At the time we compute these lists, all import lists are complete and stored with their unprotected edges. In a final walk along the boundary of *, we project vertices onto the appropriate unprotected edges, as before. 6.3.3 The Time Complexity The analysis of the above algorithm requires some topological and combinatorial results about regions. We begin with a combinatorial lemma. Let e1; e2; : : : ; ek be a sequence of k not necessarily distinct symbols. It is a DS2(n)-sequence if only n of the symbols ei are different, ei 6= ei+1 for 1 ^ i ^ k \Gamma 1, and there are no four indices 1 ^ i1 ! i2 ! i3 ! i4 ^ k so that ei1 = ei3 6= ei2 = ei4 [DaSc65]. The following is a well-known fact about the length k of the sequence. Lemma 6.8 The length of any DS2(n)-sequence is at most 2n \Gamma 1. Proof. Suppose z is the symbol that is introduced last when a DS2(n)-sequence is read from left to right. From the last part of the definition, we deduce that z occurs only once. We can thus obtain a DS2(n \Gamma 1)-sequence by either deleting z or z and its adjacent symbol. The latter case happens only when z is sandwiched between a same symbol. Clearly, induction on n completes the proof since DS2(1) = 1. 99 We use such sequences to bound the number of segments in a region *. Lemma 6.9 The number of segments of * is less than 2 r(*) + j*j. Proof. Consider the ordered sequence of segments. Replace each segment by the name of the corresponding unprotected edge. The resulting sequence contains no scattered subsequence of the form : : : ab : : :cd : : : ab : : : cd : : :; because otherwise the bounding circles of Mab and Mcd would intersect at four or more points. So if we compress repetitions we get a DS2(r(*))-sequence. If two consecutive symbols (unprotected edges) are the same then there must be a vertex of * separating them. This implies that the total number of segments exceeds the length of the DS2(r(*))-sequence by at most j*j. The total number of unprotected edges before the propagation phase is at most O(mn), and it is fairly easy to see that this bound is tight. It is plausible that a single region can have only substantially fewer unprotected edges. We now prove a more general result that implies a single region indeed cannot exceed O(m + n) unprotected edges. For a region *, we define its excess e(*) = maxf0; r(*) \Gamma 4mg. The total excess is the sum of the e(*) over all regions * of H. We prove an upper bound on the total excess which is sufficient for our purposes but certainly not tight. Lemma 6.10 The total excess is less than 36n. Proof. To help the discussion we replace each edge of G by a pair of directed edges, which we call di-edges. A di-edge pq contributes an edge to a region * if it contains the edge and along this edge * lies to the left of pq. Consider the sequence of unprotected edges in *'s boundary, and replace each such edge by the name of the contributing di-edge of G. This results in a sequence with at most 2m different symbols. A straightforward topological argument shows that there is no scattered subsequence of the form : : : pq : : : st : : : pq : : : st : : : 100 If we ignore repetitions we have a DS2(2m)-sequence, which implies that the length of the sequence without repetitions is less than 4m. Anything exceeding this number is counted by e(*). Let ab and cd be two consecutive unprotected edges contributed by the same di-edge, pq. Then (i) b = c, or (ii) bc is a protected edge of *, or (iii) there are two or more protected edges between b and c. In case (i) we can charge the projection in stage 1 for the repetition, and there are fewer than 12n of them. Each projected point is counted twice, once for each side, so we have fewer than 24n repetitions of type (i) in total. In case (iii) we can charge the vertex common to the first two protected edges after b for the repetition. This vertex must be in S [ S00. We have jS [ S00j ! 4n, and each such vertex is charged at most twice because it can lie on at most two blocking circles. This implies that there are fewer than 8n repetitions of type (iii). In case (ii), bc is a protected edge contributed by pq. We argue in the following that the total number of such edges, over all regions and di-edges, is less than 4n. This will imply the claim. Since bc is protected, its endpoints lie on a blocking circle Cj bounding Dj. Furthermore, since bc belongs to a region with at least one unprotected edge, it must be a wall. Consider Dj and the edges of H that lie on edges of G and decompose Dj. Each such edge has both endpoints on Cj. It follows that the dual graph of the decomposition is a free tree. The nodes of the tree are the regions of the decomposition, and the arcs correspond to the edges that decompose Dj. The edge bc corresponds to an arc incident to a leaf of the dual graph. We can bound the number of repetitions of type (ii) by bounding the total number of leaves of the n \Gamma 1 dual graphs defined for the blocking circles. To count the total number of leaves, we assume G is a triangulation. If not, it can be converted into one by adding fewer than 3n \Gamma m edges; adding these edges can only increase the count. The advantage of a triangulation is that now each interior node of a dual graph has degree 2 or 3. Furthermore, the number of leaves of a dual graph is 2 plus the number of degree-3 nodes. Each degree-3 node of the dual graph for Dj corresponds to a triangle of G each of whose three sides intersects Cj. A triangle can intersect at most one blocking circle in this manner. Thus, the total number of degree-3 nodes is at most the number of triangles, i.e., 2n \Gamma 5. This number plus twice the number of blocking circles is less than 4n, as claimed. 101 A region cannot have more than 4n vertices shared by adjacent protected edges, because each such vertex is a vertex in S [ S00. Each such vertex is encountered at most twice, which implies j*j ^ 2 r(*) + 8n. Lemma 6.10 thus implies a bound on the number of edges of a region. Lemma 6.11 For a region * of H, j*j = O(m + n). We are now ready to derive the time-complexity of the algorithm. Stages 1 and 2 require at most O(j*j r(*)) time per region *. By definition, r(*) ^ 4m + e(*), so the time is bounded by a constant times X j*j m + X j*j e(*); where the sums are over all regions of H. The first sum is O(m2n) because P j*j = O(mn) for H has only O(mn) edges and stage 1 adds only O(n) to this number. The second sum is O(n2) because P j*j e(*) = O((m + n) P e(*)) by Lemma 6.11 and P e(*) ! 36n by Lemma 6.10. This implies that O(m2n + n2) is an upper bound for the time spend in the first two stages of the algorithm. After that, O(m2n) time suffices to compute all import and export lists in stage 3. This implies the main result of this section. Theorem 6.12 Let G = (S; E) be a plane geometric graph with jSj = n and jEj = m * 1. A point set V of size O(m2n) that admits a completion of its Delaunay triangulation conforming to G can be computed in time O(m2n + n2). 6.4 Discussion The main result of this chapter is the existence of O(m2n) points that admit a completion of their Delaunay triangulation conforming to a plane geometric graph with n vertices and m * 1 edges. This result is superficially similar to the triangulation results of [BDE92, BEG90, BeEp91, MeSo92]. The best lower bound for the number of points necessary is \Omega (mn), and its proof is fairly straightforward. It would be interesting to close the gap between the two bounds. The O(m2n) points can be constructed in time O(m2n + n2), provided infinite precision arithmetic in constant time is assumed. This assumption is unrealistic because the number of 102 bits necessary to accurately represent a point increases at each projection along a propagation sequence. It remains open whether the points can be constructed within the same time-bound without this assumption. Acknowledgments This is joint work of Herbert Edelsbrunner and myself [EdTa92]. It benefits from communications with a few people. We are grateful to Sang-Ho Lee (Ewha Womans University, Korea) for helpful discussions during his visit at the University of Illinois, and Kurt Mehlhorn (MaxPlanck Institut, Germany), Micha Sharir (Tel-Aviv University, Israel), and Emo Welzl (Freie Universit"at Berlin, Germany) for communicating their improvement of the exponential bound described in Section 6.1. These results eventually lead to the key idea of the upper bound proof, that is, the concept of walls. 103 Chapter 7 Conclusion Many words have been said in the literature about triangulation for it is, no doubt, an important decomposition method with various applications in engineering and science. This thesis focuses on the complexity of constructing optimal triangulations. This theme has not been very popular in the literature until very recently. Because of a lack of algorithms, most previous work on constructing optimal triangulations relies on simple heuristics. This thesis substantially advances our knowledge in this respect and supplements the meager pool of algorithmic methods known to be effective in constructing triangulations. Now we can compute min-max angle, max-min height, min-max slope, min-max eccentricity, min-max length, and conforming Delaunay triangulations in low order polynomial time. Besides formulating new algorithmic and proving them correct, we also address implementation issues. All algorithms discovered are fairly simple and have interesting visual effects when animated. Roughly speaking, an edge-insertion step (Chapters 3 and 4) looks as if it is opening and then closing a hand-fan. The Subgraph approach (Chapter 5) grows triangles inside polygons. The "wall" approach (Chapter 6) marches up and down faces. We observed the behavior of an edge-insertion step from the implementation done by Roman Waupotitsch [EdWa92]; the other two approaches are not yet implemented. This thesis is certainly not the final word in the area. As discussed in Section 1.3, many questions remain open. Besides two-dimensional cases, there are many three- and higher-dimensional 104 problems; see, for example, [BeEp92, Dey91, Edel90, EdSh92, MiVa92, Raja91]. Just by going up one dimension to three, we reach another dimension of difficulty. Simple questions about the complexity of triangulating a convex polytope optimally remain open. Moreover, polytopes may not necessarily have triangulations [Sch"o28], and the corresponding decision problem is NP-complete and thus unlikely to have a polynomial time algorithm [RuSe92]. This explains some difficulties on extending the results in this thesis to higher dimensions. We leave with many words yet to be said about triangulations : : : : : : 105 Bibliography [ACNS82] M. Ajtai, V. Chv'atal, M. M. Newborn and E. Szemer'edi. Crossing-free subgraphs. Ann. Discrete Math. 12 (1982), 9-12. [AHU74] A. V. Aho, J. E. Hopcroft and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addision-Wesley, Reading, MA, 1974. [Akim84] H. Akima. On estimating partial derivatives for bivariate interpolation of scattered data. Rocky Mountain J. Math. 14 (1984), 41-52. [Aure91] F. Aurenhammer. Voronoi diagrams--A survey of a fundamental geometric data structure. ACM Comput. Surveys 23 (1991), 345-405. [BaAz76] I. Babu^ska and A. K. Aziz. On the angle condition in the finite element method. SIAM J. Numer. Anal. 13 (1976), 214-226. [BaLi84] R. E. Barnhill and F. F. Little. Three- and four-dimensional surfaces. Rocky Mountain J. Math. 14 (1984), 77-102. [Barn77] R. E. Barnhill. Representation and approximation of surfaces. Math. Software III, J. R. Rice, ed., Academic Press, 1977, 69-120. [BaSu90] I. Babu^ska and M. Suri. The p- and h-p versions of the finite element method, an overview. Comput. Methods Appl. Mech. Engrg. 80 (1990), 5-26. [BDE92] M. Bern, D. Dobkin and D. Eppstein. Triangulating polygons without large angles. In "Proc. 8th Ann. Sympos. Comput. Geom., 1992", 222-231. [BEEMT92] M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell and T. S. Tan. Edge insertion for optimal triangulations. In "Proc. 1st Latin American Sympos. Theoretical Inform., 1992", Lecture Notes in Comput. Sci. 583 (1992), 46-60. Also to appear in Discrete Comp. Geom. [BEG90] M. Bern, D. Eppstein and J. Gilbert. Provably good mesh generation. In "Proc. 31st Ann. IEEE Sympos. Found. Comput. Sci., 1990", 231-241. [BeEp91] M. Bern and D. Eppstein. Polynomial-size nonobtuse triangulation of polygons. In "Proc. 7th Ann. Sympos. Comput. Geom., 1991", 342-350. [BeEp92] M. Bern and D. Eppstein. Mesh generation and optimal triangulation. To appear in Computing in Euclidean Geometry, D. Z. Du and F. K. Hwang, eds., World Scientific, Singapore, 1992. [BFL88] J. D. Boissonnat, O. D. Faugeras and E. Le Bras-Mehlman. Representing stereo data with the Delaunay triangulation. In "Proc. Internat. Conf. Robotics and Automation, 1988", 24-29. 106 [Bois88] J. D. Boissonnat. Shape reconstruction from planar cross sections. Comput. Vision, Graphics and Image Process. 44 (1988), 1-29. [BoMu76] J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Maxmillan Press, Hong Kong, 1976. [Brow79] K. Q. Brown. Voronoi diagrams from convex hulls. Inform. Process. Lett. 9 (1979), 223-228. [BrZl70] J. Bramble and M. Zl'amal. Triangular elments in the finite element method. Math. Comp. 24 (1970), 809-820. [Cave74] J. Cavendish. Automatic triangulation of arbitrary planar domains for the finite element method. Internat. J. Numer. Methods Engrg. 8 (1974), 679-696. [Chew89] L. P. Chew. Constrained Delaunay triangulation. Algorithmica 4 (1989), 97-108. [CLR90] T. H. Cormen, C. E. Leiserson and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990. [D'AS89] E. F. D'Azevedo and R. B. Simpson. On optimal interpolation triangle incidences. SIAM J. Sci. Statist. Comput. 10 (1989), 1063-1075. [DaSc65] H. Davenport and A. Schinzel. A combinatorial problem connected with differential equations. Amer. J. Math. 87 (1965), 684-694. [Dela34] B. Delaunay. Sur la sph`ere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7 (1934), 793-800. [Dey91] T. K. Dey. Decompositions of polyhedra in three dimensions. Techn. Rep. CSD-TR-91-056, Ph.D. Thesis, Comput. Sci. Dept., Purdue Univ., IN, 1991. [DLR90a] N. Dyn, D. Levin and S. Rippa. Algorithms for the construction of data dependent triangulations. Algorithms for Approximation II, J. C. Mason and M. G. Cox, eds., Chapman and Hall, London, 1990, 185-192. [DLR90b] N. Dyn, D. Levin and S. Rippa. Data dependent triangulations for piecewise linear interpolation. IMA J. Numer. Anal. 10 (1990), 137-154. [Edel87] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, Germany, 1987. [Edel90] H. Edelsbrunner. Spatial triangulations with dihedral angle conditions. In "Proc. Internat. Workshop on Discrete Algorithms and Complexity, 1989", 83-89. [Edel92] H. Edelsbrunner. Geometric Algorithms. To appear in Handbook on Convex Geometry, P. Gruber and J. Wills, eds. [EdM"u90] H. Edelsbrunner and E. P. M"ucke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graphics 9 (1990), 66-104. [EdSh92] H. Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. In "Proc. 8th Ann. Sympos. Comput. Geom., 1992", 43-52. [EdTa91] H. Edelsbrunner and T. S. Tan. A quadratic time algorithm for the minmax length triangulation. In "Proc. 32nd Ann. IEEE Sympos. Found. Comput. Sci., 1991", 414-423. Also to appear in SIAM J. Comput. 107 [EdTa92] H. Edelsbrunner and T. S. Tan. An upper bound for the conforming Delaunay triangulation. In "Proc. 8th Ann. Sympos. Comput. Geom., 1992", 53-62. Also to appear in Discrete Comp. Geom. [EdWa92] H. Edelsbrunner and R. Waupotitsch. Optimal Two-dimensional triangulations. Animation of Geometric Algorithms: A Video Review, M. Brown and J. Hershberger, eds., Techn. Rep. 87a, Systems Research Center, DEC, Palo Alto, CA, 1992, 7-8. [ElAv81] H. ElGindy and D. Avis. A linear algorithm for computing the visibility polygon from a point. J. Algorithms 2 (1981), 186-197. [ETW90] H. Edelsbrunner, T. S. Tan and R. Waupotitsch. An O(n2 log n) time algorithm for the minmax angle triangulation. In "Proc. 6th Ann. Sympos. Comput. Geom., 1990", 44-52. Also, SIAM J. Sci. Statist. Comput. 13 (1992), 994-1008. [Fort87] S. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica 2 (1987), 153-174. [FrFi91] W. H. Frey and D. A. Field. Mesh relaxation: a new technique for improving triangulations. Internat. J. Numer. Methods Engrg. 31 (1991), 1121-1133. [FrSc87] R. Franke and L. L. Schumaker. A bibliography of multivariate approximation. Topics in Multivariate Approximation, C. K. Chui, L. L. Schumaker and F. I. Utreras, eds., Academic Press, 1987, 275-335. [GaJo79] M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, NY, 1979. [GaSo69] K. R. Gabriel and R. R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969), 259-278. [GCR77] C. M. Gold, T. D. Charters and J. Ramsden. Automated contour mapping using triangular element data structures and an interpolant over each irregular triangular domain. "Proc. SIGGRAPH, 1977". Comput. Graphics, A quarterly report of SIGGRAPH-ACM 11 (2) (1977), 170-175. [GeSh90] M. K. Georges and M. S. Shephard. Automatic mesh generator for use in two-dimensional h-p analysis. J. Comput. Civil Engrg. 4 (1990), 199-220. [Gilb79] P. D. Gilbert. New results in planar triangulations. M.S. Thesis, Dept. Comput. Sci., Univ. Illinois, Urbana, IL, 1979. [GKS92] L. J. Guibas, D. E. Knuth and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7 (1992), 381-413. [Greg75] J. A. Gregory. Error bounds for linear interpolation on triangles. The Mathematics of Finite Element and Applications II, J. R. Whiteman, ed., Academic Press, NY, 1975, 163-170. [GuSt85] L. J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graphics 4 (1985), 74-123. [Hans90] D. Hansford. The neutral case for the min-max triangulation. Comput. Aided Geom. Design 7 (1990), 431-438. [HoLe88] K. Ho-Le. Finite element mesh generation methods: a review and classification. Comput. Aided Design 20 (1988), 27-38. [Jans92] K. Jansen. One strike against the min-max degree triangulation problem. Manuscript, Fachbereich IV, Mathematik und Informatik, Universit"at Trier, Postfach 3825, W-5500 Trier, Germany, 1992. 108 [JKY92] J. W. Jaromczyk, M. Kowaluk and F. F. Yao. An optimal algorithm for constructing fiskeletons in Lp metric. To appear in SIAM J. Comput. [Joe86] B. Joe. Delaunay triangular meshes in convex polygon. SIAM J. Sci. Statist. Comput. 7 (1986), 514-539. [JoSi86] B. Joe and R. B. Simpson. Triangular meshes for regions of complicated shape. Internat. J. Numer. Methods Engrg. 23 (1986), 751-778. [JoSi87] B. Joe and R. B. Simpson. Corrections to Lee's visibility polygon algorithm. BIT 27 (1987), 458-473. [Kata88] J. Katajainen. The region approach for computing relative neighbourhood graphs in the Lp metric. Computing 40 (1988), 147-161. [Klin80] G. T. Klincsek. Minimal triangulations of polygonal domains. Ann. Discrete Math. 9 (1980), 121-123. [Lank69] P. M. Lankford. Regionalization: theory and alternative algorithms. Geog. Anal. 1 (1969), 196-212. [Laws72] C. L. Lawson. Generation of a triangular grid with applications to contour plotting. Jet Propul. Lab. Techn. Memo. 299, Pasadena, CA, 1972. [Laws77] C. L. Lawson. Software for C1 surface interpolation. Math. Software III, J. R. Rice, ed., Academic Press, NY, 1977, 161-194. [Lee83] D. T. Lee. Visibility of a simple polygon. Comput. Vision, Graphics and Image Process. 22 (1983), 207-221. [Lee85] D. T. Lee. Relative neighborhood graphs in the L1-metric. Pattern Recognition 18 (1985), 327-332. [LeLi86] D. T. Lee and A. K. Lin. Generalized Delaunay triangulation for planar graphs. Discrete Comp. Geom. 1 (1986), 201-217. [LeLi90] C. Levcopoulos and A. Lingas. Fast algorithms for greedy triangulation. Lecture Notes in Comput. Sci. 447 (1990), 238-250. [Lind83] D. A. Lindholm. Automatic triangular mesh generation on surfaces of polyhedra. IEEE Trans. Magnetics MAG-19 (1983), 2539-2542. [Ling87] A. Lingas. A new heuristic for minimum weight triangulation. SIAM J. Alg. Discrete Meth. 8 (1987), 646-658. [Lloy77] E. L. Lloyd. On triangulations of a set of points in the plane. In "Proc. 18th Ann. IEEE Sympos. Found. Comput. Sci., 1977", 228-240. [MaSo80] D. W. Matula and R. R. Sokal. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geog. Anal. 12 (1980), 205-222. [Meis75] G. H. Meisters. Polygons have ears. Amer. Math. Monthly 82 (1975), 648-651. [MeSo92] E. A. Melissaratos and D. L. Souvaine. Coping with inconsistencies: a new approach to produce quality triangulations of polygonal domains with holes. In "Proc. 8th Ann. Sympos. Comput. Geom., 1992", 202-211. 109 [MiVa92] S. A. Mitchell and S. A. Vavasis. Quality mesh generation in three dimensions. In "Proc. 8th Ann. Sympos. Comput. Geom., 1992", 212-221. [Nadl85] E. J. Nadler. Piecewise linear approximation on triangulations of a planar region. Ph.D. Thesis, Div. Applied Math, Brown Univ., RI, 1985. [NaSr91] L. R. Nackman and V. Srinivasan. Point placement for Delaunay triangulation of polygonal domains. In "Proc. 3rd Canadian Conf. Comput. Geom., 1991", 37-40. [Olou91] A. A. Oloufa. Triangulation applications in volume calculation. J. Comput. Civil Engrg. 5 (1991), 103-119. [OTZ88] S. Olariu, S. Toida and M. Zubair. On a conjecture by Plaisted and Hong. J. Algorithms 9 (1988), 597-598. [PeKe87] G. Petrie and T. J. M. Kennie. Terrain modeling in surveying and civil engineering. Comput. Aided Design 19 (1987), 171-187. [PlHo87] D. A. Plaisted and J. Hong. A heuristic triangulation algorithm. J. Algorithms 8 (1987), 405-437. [PrSh85] F. P. Preparata and M. I. Shamos. Computational Geometry--an Introduction. SpringerVerlag, NY, 1985. [QuSc90] E. Quak and L. L. Schumaker. Cubic spline fitting using data dependent triangulations. Comput. Aided Geom. Design 7 (1990), 293-301. [Raja91] V. T. Rajan. Optimality of the Delaunay triangulation in Rd. In "Proc. 7th Ann. Sympos. Comput. Geom., 1991", 357-363. [Ripp90] S. Rippa. Minimal roughness property of the Delaunay triangulation. Comput. Aided Geom. Design 7 (1990), 489-497. [Ripp92] S. Rippa. Adaptive approximation by piecewise linear polynomials on triangulations of subsets of scattered data. SIAM J. Sci. Statist. Comput. 13 (1992), 1123-1141. [RiSc90] S. Rippa and B. Schiff. Minimum energy triangulations for elliptic problems. Comput. Methods Appl. Mech. Engrg. 84 (1990), 257-274. [RuSe92] J. Ruppert and R. Seidel. On the difficulty of triangulating three-dimensional non-convex polyhedra. Discrete Comput. Geom. 7 (1992), 227-253. [Saal91] A. Saalfeld. Delaunay edge refinements. In "Proc. 3rd Canadian Conf. Comput. Geom., 1991", 33-36. [SaPe91] N. Sapidis and R. Perucchio. Delaunay triangulation of arbitrarily shaped planar domains. Comput. Aided Geom. Design 8 (1991), 421-437. [Sch"o28] E. Sch"onhardt. "Uber die Zerlegung von Dreieckspolyedern in Tetraeder. Math. Ann. 98 (1928), 309-312. [Schu87] L. L. Schumaker. Triangulation methods. Topics in Multivariate Approximation, C. K. Chui, L. L. Schumaker and F. I. Utreras, eds., Academic Press, 1987, 219-232. [Seid88] R. Seidel. Constrained Delaunay triangulations and Voronoi diagrams with obstacles. In "1978-1988, 10-Years IIG", Inst. Inform. Process., Techn. Univ. Graz, Austria, 1988, 178- 191. 110 [Shep88] M. S. Shephard. Approaches to the automatic generation and control of finite element meshes. Appl. Mech. Rev. 41 (1988), 169-185. [ShHo75] M. I. Shamos and D. Hoey. Closest point problems. In "Proc. 16th Ann. IEEE Sympos. Found. Comput. Sci., 1975", 151-162. [Sibs78] R. Sibson. Locally equiangular triangulations. Comput. J. 21 (1978), 243-245. [StFi73] G. Strang and G. Fix. An Analysis of the Finite Element Method. Prentice-Hall, Englewood Cliffs, NJ, 1973. [SuCh91] T. H. Su and R. C. Chang. Computing the constrained relative neighborhood graphs and constrained Gabriel graphs in Euclidean plane. Pattern Recognition 24 (1991), 221-230. [Supo83] K. J. Supowit. The relative neighborhood graph, with an application to minimum spanning trees. J. ACM 30 (1983), 428-448. [Tous80] G. T. Toussaint. The relative neighbourhood graph of a finite planar set. Pattern Recognition 12 (1980), 261-268. [Trac77] F. T. Tracy. Graphical pre- and post-processor for two dimensional finite element method programs. "Proc. SIGGRAPH, 1977". Comput. Graphics, A quarterly report of SIGGRAPH-ACM 11 (2) (1977), 8-12. [Voro07] G. Voronoi. Nouvelles applications des param`etres continus `a la th`eorie des formes quadratiques. Premier M'emoire: Sur quelques propri'et'es des formes quadratiques positives parfaites. J. Reine Angew. Math. 133 (1907), 97-178. [Voro08] G. Voronoi. Nouvelles applications des param`etres continus `a la th`eorie des formes quadratiques. Deuxi`eme M'emoire: Recherches sur les parall'ello`edres primitifs. J. Reine Angew. Math. 134 (1908), 198-287. [WaPh84] D. F. Watson and G. M. Philip. Survey on systematic triangulations. Comput. Vision, Graphics and Image Process. 26 (1984), 217-223. [Waup92] R. Waupotitsch. Implementation and performance analysis of the minmax angle algorithm. M.S. Thesis, Dept. Comput. Sci., Univ. Illinois, Urbana, IL, 1992. [WGS90] F. W. Wilson, R. K. Goodrich and W. Spratte. Lawson's triangulation is nearly optimal for controlling error bounds. SIAM J. Numer. Anal. 27 (1990), 190-197. [WWW85] P. Widmayer, Y. F. Wu and C. K. Wong. Distance problems in computational geometry with fixed orientation. In "Proc. 1st Ann. ACM Sympos. Comput. Geom., 1985", 186-195. [Yao82] A. C. Yao. On constructing minimum spanning trees in k-dimensional space and related problems. SIAM J. Comput. 11 (1982), 721-736. 111 Vita Tan, Tiow Seng was born on 2 November 1962 in Muar, Johor, Malaysia. He was brought up in the neighboring country, Singapore. He received a B.Sc. majoring in Computer Science and Mathematics from the National University of Singapore in April 1984. He also received the Data Processing Managers' Association Award (1984). Upon graduation, he was employed by the National Computer Board, Singapore, as an Information System Officer at the Ministry of Health. In November 1985, Tan returned to the National University of Singapore as a Senior Tutor in the Department of Information Systems and Computer Science. He then finished a M.Sc. before going on a study leave at the University of Illinois in January 1988. His study leave was supported by a National University of Singapore Oversea Graduate Scholarship. Tiow-Seng completed a Ph.D. in Computer Science in December 1992. He also received the C. W. Gear Outstanding Graduate Student Award (1992). He has since returned to the Department of Information Systems and Computer Science, National University of Singapore, Lower Kent Ridge Road, Singapore 0511, Republic of Singapore (email: tants@iscs.nus.sg). 112