Straight skeleton of a simple polygon

[Franz Aurenhammer]

The straight skeleton of a simple polygon is defined by shrinking the polygon by translating each of its edges at a fixed rate, keeping sharp corners at the reflex vertices, and watching where the vertices go. The straight skeleton is quite similar to the medial axis; in fact, the two are equivalent for convex polygons. However, the straight skeleton of a nonconvex polygon has fewer edges than the medial axis, and all its edges are line segments; the medial axis also has parabolic arcs around each reflex vertex. On the other hand, unlike the medial axis, the straight skeleton is not a Voronoi diagram in any sense.

The straight skeleton can be used to construct a polygonal roof over a set of ground walls [1], reconstruct a geographical terrain from a river map, or define a pattern of of folds that will make all the edges of a paper polygon colinear (although this last property is true of other "bisector graphs" [1] as well; see also [6]). The definition of straight skeleton can be generalized to arbitrary planar straight line graphs [2], where it has (potential) applications to planar motion planning, and to three-dimensional polyhedra, where it has potential applications to solid modelling.

Although the medial axis can be constructed in linear time [3], the fastest known algorithms for stright skeletons are much slower. The main difficulty is that changing the positions or angles of reflex vertices has a significant non-local effect on the skeleton. This nonlocality makes techniques such as incremental construction or divide-and-conquer fail. The following table lists the time and space bounds of various algorithms. Here n is the total number of vertices, r is the number of reflex (nonconvex) vertices, and e is an arbitrarily small positive constant.

Time Space Ref.
O(n2 log n) O(n) [2]
O(nr log n) O(nr) [1,5]
O(n log n + nr log(n/r)) O(nr) [1,4,5]
O(n log n + nr + r2 log r) O(n) [2,5]
O(n log n + nr) O(n + r2) [1,4,5]
O(n1+e + n8/11+er9/11+e) O(n1+e + n8/11+er9/11+e) [5]

Note that the last algorithm is subquadratic in the worst case. It seems rather unlikely that this is the fastest possible algorithm, even ignoring the ne factors. However, no nontrivial lower bound is known in any model of computation.

Is there a near-linear-time algorithm to construct the straight skeleton? This might be too mcuh to hope for in the general case; perhaps O(n4/3) or O(n3/2) is the right time bound. There are already near-linear-time algorithms for two special cases: c-oriented polygons (where each edge is parallel to one of constant number of lines) [5] and polygons with very few reflex vertices. Another special case that seems likely to have a fast solution is polygons whose smallest (external) reflex angle is at least 90 degrees, or even just bounded away from zero.

For a similar problem, which (I believe) formalizes what makes constructing the straight skeleton hard, see "Crashing Motorcycles Efficiently".

References

  1. Oswin Aichholzer, Franz Aurenhammer, David Alberts, and Bernd Gärtner, "A Novel Type of Skeleton for Polygons", Journal of Universal Computer Science 1(12), pp. 752-761, 1995.

  2. Oswin Aichholzer and Franz Aurenhammer, "Straight Skeletons for General Polygonal Figures in the Plane", Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96), Lecture Notes in Computer Science 1090, Springer, pp. 117-126, 1996.

  3. Francis Chin, Jack Snoeyink, and Cao An Wang, "Finding the Medial Axis of a Simple Polygon in Linear Time", Proc. 6th Ann. Int. Symp. Algorithms and Computation (ISAAC 95) , Lecture Notes in Computer Science 1004, pp. 382-391, 1995.

  4. David Eppstein, "Fast hierarchical clustering and other applications of dynamic closest pairs", manuscript, July 1997.

  5. David Eppstein and Jeff Erickson, "Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions", manuscript, July 1997.

  6. Robert Lang, "A Computational Algorithm for Origami Design", Proc. 12th Ann. ACM Symp. Computational Geometry, pp. 98-105, 1996.
Open Problems - Jeff Erickson (jeffe@cs.duke.edu) 11 Jul 97