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 mid90s by Aichholzer et al.^{1} and its definition is closely related to miteredoffset curves.
Consider the black polygon above. The gray subpolygons 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 straightline graphs.
Aichholzer et al. also gave a different way of looking at the straight skeleton: If we embed the wavefront propagation into threedimensional space where the zaxis is time, then the wavefront traces out a threedimensional roof shape. This is the socalled 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:
 Computing mitered offset curves and toolpath generation in CAD/CAM.
 Shape reconstruction and contour interpolation of threedimensional bodies, e.g., in medical imaging.
 Automatic generation of hip roofs and variants for buildings.
 Landscape generation of mountain terrain.
 Solving foldandcut problems in the field of mathematical origami.
 Topologypreserving map simplification and extraction of centerlines of roads in geographic information systems.
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:
Our contribution.

Computing motorcycle graphs. A motorcycle graph is a geometric structure that is in a close relationship with straight skeletons.
In [HuHe09, HuHe11b] we presented an algorithm for computing motorcycle graphs based on geometric hashing. A stochastic analysis shows that on average the algorithms runs in O(n log n) time if the motorcycles are distributed uniformly enough. Outside the convex hull of the start points of the motorcycles the algorithm runs in deterministic O(n log n) worst case time. The resulting implementation MOCA has been extensively tested and shows an O(n log n) runtime for the vast majority of input files in our database of 22.000 datasets of various characteristics, including industrial data.
In [MHH12] we investigated kinetic triangulations in order to compute motorcycle graphs. The main advantage of this approach is that its runtime is less sensitive to the distribution of the motorcycle. Experimental results (the implementation was done by Willi Mann) show virtually no outliers from an O(n log n) runtime behavior.

Triangulationbased algorithm. Aichholzer and Aurenhammer^{2} presented a straightskeleton algorithm that simulates the wavefront by means of a kinetic triangulation. A big open problem is the exact worstcase runtime complexity of this algorithm, which is known to be somewhere between O(n³ log n) and O(n² log n).
In [HuHe10], we investigated the number of socalled flip events in these kinetic triangulations. We were able to show that polygons exist where a linear number of diagonals are flipped each a linear number of times. Furthermore, polygons exist where every triangulation leads to a quadratic number of flip events and even retriangulating does not help to save computing time. The most import result is, however, that Steiner triangulations of polygons exist were no flip events exist at all.
While the best known bound for the worstcase time complexity is still O(n³ log n), it has been unclear how well this algorithm would actually perform for practical input data. In [PHH12], we report on experimental results of an carefully engineered implementation of this algorithm by Peter Palfrader. It turned out that some nontrivial algorithmic gaps needed to be filled in order to actually turn the algorithm into an implementation.

Motorcycle graphs and straight skeletons. In [HuHe11c], we proved that a motorcycle graph can be simulated by straight skeletons. This is interesting as lower bounds of motorcycle graphs can therefore be transferred to straight skeletons. In particular, the Pcompleteness of straight skeletons follows from the Pcompleteness of motorcycle graphs. Hence, there are no efficient parallel algorithms for straight skeletons. These results were already mentioned by Eppstein and Erickson^{3}.
In [HuHe11, HuHe12], we proved that the straight skeleton of an arbitrary planar straightline graph can be defined as the lower envelope of partially defined linear functions via a generalization of the motorcycle graph. This result generalizes partial results by Eppstein and Erickson^{3} resp. Cheng and Vigneron^{4}. As a result, the straight skeleton can be computed by means of graphics hardware using a similar technique as Hoff et al.^{5} describes for Voronoi diagrams.
This result also forms the foundation for our straightskeleton algorithm and its implementation STALGO. STALGO was the first implementation that ran in O(n log n) runtime for practical input data on an industrialstrength reliability level. Compared to the straightskeleton code in CGAL, STALGO is by a linear factor faster and uses by a linear factor less memory. For datasets with a 10.000 vertices, STALGO runs by two to three orders of magnitudes faster and uses less than 100 Mb of RAM, instead of 10 GB.

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

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

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):569592, 1999. ↩ ↩^{2}

S.W. Cheng, A. Vigneron, Motorcycle Graphs and Straight Skeletons, Algorithmica, 47(2):159182, 2007 ↩

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