We present a simple algorithm for computing straight skeletons of planar straight-line graphs. We exploit the relation between motorcycle graphs and straight skeletons, and introduce a wavefront-propagation algorithm that circumvents the expensive search for the next split event. Our algorithm maintains the simplicity of the triangulation-based algorithm by Aichholzer and Aurenhammer but has a better worst-case complexity of O(n 2 logn). Preliminary experiments with our implementation demonstrate that an actual runtime of O(n logn) can be expected in practice.
['Stefan Huber', 'Martin Held']
Computing straight skeletons of planar straight-line graphs based on motorcycle graphs.