Onion triangulations
Given a set of points on the plane, the goal is to obtain a triangulation of that set of points.
Much research has been done to improve the efficiency of triangulation algorithms, from Lennes's original algorithm (1911) having quadratic time complexity to Chazelle's algorithm (1991) has linear time complexity.
The focus here is on a specific type of triangulation, based on the onion-peeling of a set of points.
Consider a set S of n on the plane. Compute the convex hull of S, and let S' be the set of points remaining in the interior of the hull. Compute then the convex hull of S' and recursively repeat this process until no more points remain. One ends up with a sequence of nested convex hulls, called the onion-peeling of S. This structure can be obtained in O(n log n) time, thanks to an algorithm by Chazelle.
The onion-peeling of a set of points. Note that the innermost structure can either be a line segment or a single point, besides a convex polygon. This graph gives information as to the layering of the points, i.e. how "deep" points are relative to each other other.
The region between two nested convex hulls is called an annulus. Toussaint (1986) presents a simple algorithm for triangulating an annulus, using the Rotating Calipers. Using his method, once the onion peeling has been obtained, the entire set can be triangulated in linear time. Furthermore, the triangulation has two advantages: it keeps the onion-peeling as a subgraph, and it is hamiltonian, that is the dual of the triangulation graph is a chain.
The algorithm for triangulating an annulus is quite simple. The input is assumed to be a convex hull Q nested in an other hull P, both given in clockwise order.
- Insert the edges of the hulls as edges in the triangulation.
- Compute the points with minimum x coordinate for both P and Q, calling them xmin(P) and xmin(Q).
- Construct two vertical lines of support (the calipers) at xmin(P) and xmin(Q); call them LP and LQ.
- Insert (xmin(P), xmin(Q)) as an edge in the triangulation.
- The "current" points p and q for LP and LQ are xmin(P) and xmin(Q), respectively.
- Rotate the lines clockwise until one coincides with an edge. A new vertex has therefore been "hit" by one of the lines.
- If it belongs to P (call it p'), insert (p', q) into the triangulation. Update the "current" points to p' and q.
- If it belongs to Q (call it q'), insert (p, q') into the triangulation. Update the "current" points to p and q'.
- In case of parallel edges, both lines of support coincide with edges, and two new vertices are "hit" (call them p' and q'). Then, insert (p', q'), and either (p, q') or (p', q) into the triangulation. Update the "current" points to p' and q'.
- Repeat the previous step until the starting minimum points are reached.
An example of a triangulated annulus is shown below:
The above algorithm has linear time complexity. When used to triangulate a set of points, a single convex hull is run (at most) twice through the procedure, once as the inner hull of the annulus, and once as the outer. Then the entire running time for triangulating a set of n points remains O(n).
Another specific and closely related triangulation is the spiral triangulation based on the convex spiral of a set of points.
December 17th, 1998