From:Peter Yamamoto <pjyamamo@watdragon.uwaterloo.ca>Subject:Re: RGI lecture notesDate:Wed, 18 Aug 1993 13:30:31 -0400 (EDT)

"Triangulations and Arrangements" Godfried Toussaint McGill University All Institute Lecture July 12, 1993 Scribes: Laura Anderson, Peter Yamamoto Assistant Editor: Pedro Ramos Professor Toussaint's lecture discussed algorithms for triangulating simple polygons in the plane. A polytope in higher dimensions may not have any triangulation, but for a two-dimensional polytope a triangulation always exists. Several algorithms for computing a triangulation were discussed including a short history of published but incorrect algorithms. The first talk was limited to triangulations; arrangements were discussed in another lecture. ------------------------------------------------------------ First, some definitions: A _diagonal_ of a polygon is a line segment which connects two vertices of the polygon and which lies entirely inside the polygon. A _triangulation_ of a polygon is a decomposition of the polygon into non-overlapping triangles by diagonals. Note that there are (n-3) non-intersecting diagonals which divide the polygon into (n-2) non-overlapping triangles. A fundamental lemma states that any polygon with n > 3 vertices can be partitioned into two sub-polygons by inserting some diagonal of P. First, note that this lemma does not generalize to higher dimensions. A simple example, due to Sch\"onhardt in 1928, is constructed by twisting a prism. Construct a triangular prism in three dimensions by using an equilateral (say of unit length) triangle base in the xy plane and a copy of the base elevated above it (say translated by unit length). Finish the prism by attaching the two triangles with vertical edges. Now rotate one of the triangular faces 30 degrees about the vertical axes, twisting the edges connecting the two triangles. The resulting polytope, with eight triangular faces, cannot be triangulated. In fact, one cannot add even one diagonal without breaking up a triangular face. Second, despite the simplicity of the lemma, many published proofs of it, or triangulation algorithms based on the lemma, are incorrect. Professor Toussaint outlined three such errors. For a more detailed discussion the reader is referred to [Ho]. ----------------------------------------------------------------------- Algorithms That Don't Work (But Made It Into Print): First, Professor Toussaint noted that geometric algorithms, step by step constructions using primitive operations, dates back to Euclid. He also noted that despite this careful description of a construction some algorithms do not always work. There are a family of triangulation algorithms (or constructive proofs of the lemma) which follow the same general approach: at each step, either cut off one empty triangle or add one diagonal. The algorithm is then repeated on the resulting sub-polygon(s). We first label the vertices of the polygon x(1), x(2),...,x(n) so that for every i, the vertices x_i and x_{i+1} have an edge between them. Find vertex x_i with leftmost x-coordinate Look at the triangle [x_{i-1},x_i,x_{i+1}] formed by joining the two adjacent vertices. Step 1. If there are no other vertices inside that triangle then the triangle [x_{i-1},x_i,x_{i+1}] is empty so delete the triangle and repeat Step 1 on the resulting subpolygon. Step 2. Otherwise there is at least one vertex in the triangle. Hence there is some vertex x(k) which can be joined to x_i with a diagonal thus splitting the polygon into 2 subpolygons. Repeat Step 1 on the two subpolygons. There have been several published methods for handling Case 2. Most are based on an intuition which goes wrong. ------------------------------------------------------------------------- Question: Do you have any ideas for determining how to join x_i to another vertex to form a diagonal? -------------------------------------------------------------------------- Intuition 1: Find an empty sub-triangle of [x_{i-1},x_i,x_{i+1}] by rotating a ray anchored at x_i from x_{i-1} to x_{i+1}. Since there is at least one vertex in the triangle, the ray will hit some vertex in this rotation. Suppose x(k) is the first such vertex. Then the triangle [x_{i-1},x_i,x(k)] doesn't contain any other vertices inside of it (otherwise such a vertex would have been hit by the ray). So connect x_i to x(k). Intuition 2: If there is a vertex in the triangle then there must be a vertex closer to x_i than any other vertex (other than x_{i-1} and x_{i+1}). So find the closest vertex x(k) in the triangle and join x_i to x(k). Intuition 3: Find the leftmost vertex x(k) inside the triangle and join x_i to x(k). Hints are at the end, but try to draw counterexamples to each of the intuitions by yourself. ---------------------------------------------------------------------- A 20th-Century proof that Triangulations Always Exist We define a vertex x_i of a polygon P to be _principal_ if the triangle with vertices {x_{i-1}, x_i, x_{i+1}} is empty. If such a vertex is a concave point of P we call it a _mouth_ else it is convex and we call it an _ear_. THE TWO-EARS THEOREM (Meister, 1975): Every simple polygon with at least four sides contains at least two non-overlapping ears. Meister provided a constructive proof which also provides a correct but slow algorithm for triangulating the polygon. Well, that's o.k. for mathematicians but computer scientists were still unhappy... Another proof is based on properties of the _dual graph of a triangulation_. Consider a point inside each triangle. Attach one point to another if their triangles share a side. Note that a triangle can share one, two, or three sides. Furthermore note that the dual graph must be a tree since if not, it has a cycle, and this would represent a hole in the polygon which is not allowed (triangulation of polygons with holes is another matter). Now note that a leaf in the dual tree corresponds to a triangle with only one adjacent triangle: an ear. Since a tree with more than one node always has at least two leaves, the triangulation must also have at least two ears. The theorem suggests a method for triangulating: ``find an ear and cut it off''. This gives a correct but long algorithm for triangulating: searching for ears to cut off can be very time-consuming. In the worst case, triangulating a polygon this way can take O(n^3) time. ------------------------------------------------------------------ Some Algorithms That Do Work (And Are Faster Than Cutting Off Ears) In a simple polygon, we can always find either an ear or a diagonal in O(n) time. Procedure DIAGONAL Input: A simple polygon P oriented in a counterclockwise direction. Output: Polygon P with a diagonal inserted in P. Step 1. Find a convex vertex x_i of P. Step 2. Construct a ray at x_i, ray(x_i), that bisects the interior of angle(x_{i-1}x_ix_{i+1}). Step 3. Find the first intersection point, called y, of ray(x_i) with the boundary of P, bd(P). y is on some edge [x_j,x_{j+1}] of P. Step 4. Construct the triangle [x_i,y,x_{j+1}]. Step 5. For all j+1 < k < i, if x_k lies in triangle [x_i,y,x_{j+1}] then label x_k as x*_k. If there are no labeled vertices then exit with [x_i,x_j+1] as the diagonal. Step 6. For all labeled vertices, compute angle(y,x_i,x*_k) and select that vertex, call it z, which minimizes the angle. If z <> (is not equal to) x_{i-1}, then exit with [x_i,z] as the diagonal. Step 7. Construct the triangle [x_j,y,x_i]. Step 8. For all j > k > i, if x_k lies in triangle [x_j,y,x_i] then label x_k as x*_k. If there are no labeled vertices, exit with [x_i,x_j] as the diagonal. Step 9. For all labeled vertices compute angle(y,x_i,x*_k) and select that vertex, call it w, that minimizes this angle. If w <> x_{i+1} then exit with [x_i,w] as the diagonal. Step 10. Exit with [x_{i-1},x_{i+1}] as the diagonal. This procedure can then be used to triangulate in O(n^2) time. To get an algorithm that works in better than O(n^2) time, let's first consider the special case of a convex polygon. An O(n) algorithm for triangulating it would be to start at some edge {x_i, x_{i+1}}, then add either the triangle {x_{i-1}, x_i, x_{i+1}} or the triangle {x_i, x_{i+1}, x(i+2)} to our triangulation. Then we repeat this with the edge we just added, and continue until the whole polygon is triangulated. Note that at every step we made a choice of which triangle to add. Consider the triangulation of the convex polygon that results from joining every second vertex (remember the vertices of P are given as an ordered sequence) to a fixed vertex and then joining every second vertex with an edge. In this case the dual tree has O(n) internal nodes and O(n) leaves. Now consider the triangulation of the same convex polygon obtained by drawing all diagonals from one fixed vertex to all the vertices (this is possible because of the convexity) resulting in a triangulation that looks like a fan. In this case, note that the dual tree is very simple: it is simply a chain since each triangle, except for the first and last, has two adjacent triangles. A triangulated polygon whose dual tree is a chain is called a sleeve. A convex polygon always has a triangulation which is a sleeve. The above triangulation process generalizes to simple polygons by trying to triangulate subpolygons which are sleeves; these sleeves are then joined together by triangles which are adjacent to three triangles. A diagonal, d, is inserted and the triangulation process (join an adjacent vertex) starts at d assuming the part of the polygon it is triangulating is indeed a sleeve. Eventually the algorithm may discover that it made a mistake (we are not in a sleeve) so it backtracks until the triangulated portion is really a sleeve. Now we know that this sleeve must be connected to the rest of the triangulation by adding two diagonals instead of just one. So we add two diagonals and continue the sleeve searching from those two diagonals. This process will triangulate any simple polygon in O(n(1+t_0)) time, where t_0 is the number of triangles in our output that have no edges on the boundary of the polygon. Note that these _free triangles_ correspond to degree 3 vertices in the dual graph (they have 3 edges). In the worst case, there may be O(n) free triangles hence the algorithm has worst case time complexity of O(n^2). Since an O(n) time algorithm for triangulating _any_ simple polygon has been found (a milestone in geometric computation), one may ask 'Why is such an algorithm, with time complexity dependent on the output triangulation, of any interest?' The main reason is that the algorithm is more straightforward than other algorithms (in particular the O(n) result is quite complicated and hard to implement), and for certain classes of polygons it will always run in O(n) time. Professor Toussaint next outlined a brief history of triangulation algorithms culminating in the recent O(n) algorithm by Chazelle. But he didn't end on that note, rather, he described two more results on polygon triangulation. -------------------------------------------------------------------- The Complexity History of Triangulating a Simple Polygon 1) 1911 Lennes (American Math Journal but very computational essay) O(n^2) via recursive diagonal insertion. Question: Why was Lennes considering the triangulation problem in 1911? 2) 1975 Meister O(n^3) via "ear-cutting" 3) 1978 Garey, Johnson, Preparata, Tarjan O(n log n) via decomposition into monotone pieces. 4) 1982 Chazelle O(n log n ) via divide-and-conquer technique. 5) 1983 Herbert and Mehlhorn O(n + r log r ) where r is the number of reflex vertices. 6) 1983 Chazelle O(n log s) where s is the sinuosity of P. 7) 1987 Tarjan and Van Wyk O(n log log n) via "involved" data structures. 8) 1988 Toussaint O( n (1 + t_0)) via sleeve searching where t_0 is the number of "free triangles" in the output triangulation. 9) 1990 ElGindy, Everett, Toussaint Finding an ear in O(n) time via "prune and search" technique implies algorithm 2) can be done in O(n^2) time. 10) 1990 Chazelle O(n) via very "involved" techniques. Essentially unimplementable. ---------------------------------------------------------------------------- Is triangulation of a simple polygon history? No, not really. Certainly the most important complexity question has been answered by Chazelle, but fast practical algorithms are still desired by industry where practical may depend on the specific application. Professor Toussaint went on to outline some of the other aspects of the triangulation polygon in particular classes of polygons which can be triangulated in linear time. Only a brief review of topics are listed as this "summary" is running a bit long. A Palm-Shaped Polygon with respect to a point O is a polygon such that the shortest geodesic path from O to any point is either right turning or left turning. This implies that the polygon may be split into left palm subdivisions and right palm subdivisions. Now Professor Toussaint went into an aside regarding the computation of the convex hull of a polygon using the Graham scan (an algorithm for finding the convex hull of a set of points). ASIDE: Convex Hull via Graham Scan [Graham] 3-coin description Find smallest x-coordinate vertex. Place coin on it and next two vertices. (or was it a convex turn?) If three coins form a right turn Then back coin goes to the front Else (if left turn) middle coin goes back (if it can: can't go back behind starting vertex) and delete middle vertex. OBSERVATION: The Graham scan triangulates CH(P) \ P. Problem: Graham scan works well for star-shaped polygons but can have problem with simple polygon: => Bad polygon for Graham Scan (see if you can find a polygon on which the Graham scan fails). END of ASIDE: A right palm with respect to a point x. Exercise: Show that you can always triangulate with the 3-coins algorithm. (I guess he was running out of time). Question: How hard is it to determine palm-shaped-ness? Answer: You can find the "kernel" of a palm polygon in linear time. So we can triangulate palm-shaped polygons in linear time. In fact, the palm shaped polygons themselves contain several other classes of polygons. But that's not all... Palm Decomposition of a Monotone Polygon Given a direction in which P is monotone P can be decomposed in linear time into the union of left and right palm polygons. Hence, monotone polygons may also be triangulated in linear time using the simple 3-coins algorithm as a procedure. ----------------------------------------------------------------------- Computing Bushy and Thin Triangulations Shermer 1988 Thin triangulation minimizes the number of degree 3 vertices in dual. Bushy triangulation maximizes the number of degree 3 vertices in dual. Algorithms: Bushy: O( T(n) ) and O(n) space where T(n) is the time for triangulating. Thin: O(n^3). Problem: Can you do better for finding a thin triangulation? ----------------------------------------------------------------------- Triangulating a Set of Points Does it always exist? Idea: First, draw a simple polygon through the points. Second, triangulate inside and outside separately. Question: Can you always draw a simple polygon through a set of points? Answer: Yes. Choose 2 points such that no 3rd is collinear. Sort the other points with respect to perpendicular projection onto line through the two points. ----------------------------------------------------------------------- Triangulating a set of Line Segments What is it?! A triangulation of the end points of the segments such that the segments are edges in the triangulation. Idea: First, draw a simple polygon through the line segments... But that is not always possible. [Counter example: Existence of "Cutting line segment" means can't do it. "Cutting line segment": diagonal of the CH of the line segments]. Problem: So how to compute the triangulation? ----------------------------------------------------------------------- At this point Professor Toussaint was out of time. The last few topics covered shows that there are still interesting triangulation problems to be considered. Two references are provided which contain more extensive bibliographies related to the material presented. [Ho] @article{h-dpt-76 , author = "C.-W. Ho" , title = "Decomposition of a polygon into triangles" , journal = "Math. Gazette" , volume = 60 , year = 1976 , pages = "132--134" , keywords = "decomposition, polygon triangulation, elementary geometry" , cites = "l-tsfpp-11" , annote = "A short correct proof of decomposability." } [To] @inproceedings{t-ocspt-90, , author = "G. T. Toussaint" , title = "An output-complexity-sensitive polygon triangulation algorithm" , year = 1990 , comments = "Published version of t-ocspt-90" , booktitle = "CG International '90 Computer Graphics Around the World" , publisher = "Springer-Verlag" , year = 1990 , pages = "443--466" , keywords = "triangulation, shape-complexity" Hints for intuitions gone wrong. The hint for all three counterexamples is that while x(k) may be a vertex which forms a triangle with no other vertices inside of it, it doesn't mean that there are no _edges_ cutting through the triangle! In other words, x(k) is separated from x(i) by some edge. Given that hint, the trick simply lies in constructing the polygon with an edge between x(i) and x(k) such that the vertices of that edge (or edges connecting it to the rest of the polygon) do not violate the "empty" conditions in the intuition.