From: Peter Yamamoto <pjyamamo@watdragon.uwaterloo.ca>
Subject: Re: RGI lecture notes
Date: 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.