Spiral triangulations
The spiral triangulation of a set of points is a triangulation graph based on the convex spiral of that set.
The convex spiral is obtained in the following way:
- Start at a given extreme point (i.e. the minimum point in a given direction), say the point with minimum x coordinate
- Construct a vertical line through that point.
- Rotate the line in a fixed direction (always clockwise or always counterclockwise), until the line "hits" another vertex.
- Join the two points by a line segment.
- Repeat steps 3 and 4, but always ignoring points already hit.
In essence, the procedure somewhat resembles the gift-wrapping algorithm for computing convex hulls, but with the difference that the loop is never closed. For a set of points whose hull has h points, 2h convex spirals exist: for each starting point there exists a clockwise and a counterclockwise spiral.
A set of points (left), and its clockwise convex spiral, with minimum x coordinate point as the starting point.
Interestingly, the convex spiral and the onion-peeling of a set can be obtained one from the other in linear time. Furthermore, similar to the onion triangulation, one defines the spiral triangulation of a set of points, whose subgraph is the convex spiral.
The algorithm for obtaining the spiral triangulation, although based on the annulus triangulation algorithm, is somewhat more complicated, as the spiral must be split into proper convex chains. The input is assumed to be a clockwise convex spiral C of a set, with C={p1, ..., pn}.
- Insert the edges of the convex spiral as edges in the triangulation.
- Starting with p1, find the point ph being the last point on the convex hull of the set of points.
- Extend the last edge of the convex spiral [p(n-1),pn] until it intersects the convex spiral. Label that point q'.
- Construct the line locally tangent to C at q'. Rotate the line counterclockwise until it hits the first point of C such that the line is parallel to [p(n-1),pn]. Label this point q.
- Insert [p(n-1),q] into the triangulation.
- This construction splits the convex spiral into two regions: the outer spiral region and the inner polygonal region. Let Co={p1, ... ,q} and let Ci={ph, ... ,q, ... , pn}. The construction is illustrated below:
Top left: the construction. Top right: the outer spiral and the inner polygonal regions. Bottom: The outer and inner convex chains Co and Ci.
- The outer spiral region is triangulated as an annulus. Co and Ci can be locally viewed as nested convex hulls.
- The inner polygonal region is starshaped at pn and therefore easily triangulated.
- The union of these two triangulations form the complete spiral triangulation.
An example of a convex spiral and its triangulation is shown below:
The above algorithm has linear time complexity, based on the running time of the annulus triangulation algorithm.
December 17th, 1998