Straight skeletons for general polygonal figures

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 Proc. $2^{nd}$ Ann. Int'l. Computing and Combinatorics Conf. COCOON'96, Lecture Notes in Computer Science, volume 1090, pages 117-126, Hong Kong, 1996. Springer Verlag. [IIG-Report-Series 423, TU Graz, Austria, 1995].