Straight skeletons and motorcycle graphs

Introduction. The straight skeleton of a simple polygon is, like the Voronoi diagram, a tree structure within the polygon. It has been introduced to computational geometry in the mid-90s by Aichholzer et al.1 and its definition is closely related to mitered-offset curves.

Definition of a straight skeleton

Consider the black polygon above. The gray sub-polygons show a wavefront process where every edge is moving inwards with constant speed. And while this wavefront propagates some edges may vanish and other edges may split, until the wavefront vanishes. If you trace the movement of every wavefront vertex, you obtain the straight skeleton (blue). This definition was later extended from polygons to planar straight-line graphs.

Aichholzer et al. also gave a different way of looking at the straight skeleton: If we embed the wavefront propagation into three-dimensional space where the z-axis is time, then the wavefront traces out a three-dimensional roof shape. This is the so-called terrain model or roof model as shown in the right subfigure.

Applications. Similar to Voronoi diagrams, straight skeletons have a lot of applications in different research areas. An incomplete list comprises:

From input via straight skeletons to offset curves

A comprehensive overview on the research of straight skeletons and motorcycle graphs up to the year 2011 is given in my book Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice published at the Shaker Verlag:

thesis

Our contribution.

  1. O. Aichholzer, D. Alberts, F. Aurenhammer, B. Gärtner, A Novel Type of Skeleton for Polygons, Journal of Universal Computer Science, 1(12):752-761, 1995. 

  2. O. Aichholzer, F. Aurenhammer, Straight Skeletons for General Polygonal Figures in the Plane, Voronoi’s Impact on Modern Science, Book 2, pp. 7-21, Inst. of Math. of the Nat. Acad. of Sci. of Ukraine, 1998. 

  3. D. Eppstein, J. Erickson, Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions, Discr. and Comp. Geometry, 22(4):569-592, 1999.  2

  4. S.-W. Cheng, A. Vigneron, Motorcycle Graphs and Straight Skeletons, Algorithmica, 47(2):159-182, 2007 

  5. K. Hoff, T. Culver, J. Keyser, M. Lin, D. Monacha, Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware, SIGGRAPH’99, pp. 277-286, 1999.