Straight skeletons for general polygonal figures in the plane

O. Aichholzer and F. Aurenhammer


A novel type of skeleton for general polygonal figures, the straight skeleton $S(G)$ of a planar straight line graph $G$, is introduced and discussed. Exact bounds on the size of $S(G)$ are derived. The straight line structure of $S(G)$ and its lower combinatorial complexity may make $S(G)$ preferable to the widely used Voronoi diagram (or medial axis) of $G$ in several applications. We explain why $S(G)$ has no Voronoi diagram based interpretation and why standard construction techniques fail to work. A simple $O(n)$ space algorithm for constructing $S(G)$ is proposed. The worst-case running time is $O(n^3 \log n)$, but the algorithm can be expected to be practically efficient, and it is easy to implement. We also show that the concept of $S(G)$ is flexible enough to allow an individual weighting of the edges and vertices of $G$, without changes in the maximal size of $S(G)$, or in the method of construction. Apart from offering an alternative to Voronoi-type skeletons, these generalizations of $S(G)$ have applications to the reconstruction of a geographical terrain from a given river map, and to the construction of a polygonal roof above a given layout of ground walls.

Reference: O. Aichholzer and F. Aurenhammer. Straight skeletons for general polygonal figures in the plane. In A. Samoilenko, editor, Voronoi's Impact on Modern Sciences II, volume 21, pages 7-21. Proc. Institute of Mathematics of the National Academy of Sciences of Ukraine, Kiev, Ukraine, 1998.