Computing straight skeletons and motorcycle graphs

Mehr zum Buch

The straight skeleton is a geometric structure introduced to computational geometry in the mid-90s, with applications in various fields, including mitered offset curves, roof model generation, and geographic map contraction. Currently, there exists a significant gap between the known lower bound on the time complexity of computing straight skeletons and the most efficient algorithms. To bridge this gap, more efficient algorithms and implementations are needed. This thesis aims to establish theoretical foundations for developing the straight-skeleton algorithm behind Bone, a state-of-the-art implementation. After surveying the current research, we analyze the triangulation-based approach by Aichholzer and Aurenhammer, which leads us to generalize the motorcycle graph from non-degenerate polygons to arbitrary planar straight-line graphs. This generalization allows us to extend the nonprocedural characterization by Cheng and Vigneron. We introduce a novel wavefront-type algorithm that is efficient in time and space, suitable for real-world applications, and operates on arbitrary planar straight-line graphs, achieving a better worst-case complexity than the triangulation-based algorithm. Our C++ code, Bone, outperforms previous implementations, handling more general input and being faster and more space-efficient. In the second part, we focus on the practical computation of the generalized motorcycle graph, presenting a simple alg