Huber, S: Computing Straight Skeletons and Motorcycle Graphs

The straight skeleton is a geometric structure which was introduced to the field of computational geometry in the mid-90s. Similar to the generalized Voronoi diagram, it features a rich variety of applications in diverse domains, such as the computation of mitered offset curves, the generation of roof models and terrains, the reconstruction of three-dimensional bodies from parallel slices, the topologypreserving contraction of areas in geographic maps, and many more. However, at the moment one faces a significant gap between the best known lower bound on the time complexity of computing straight skeletons and the most efficient algorithms and implementations. Hence, in order to bridge the gap between the current state of theory and its real-world applications in science and industry, we need more efficient algorithms and implementations. The main goal of this thesis was to lay the theoretical foundations that finally allowed us to develop the straight-skeleton algorithm behind Bone, our current state-of-the-art implementation of straight skeletons.After an elaborate survey on the current state of research on straight skeletons and its geometric properties, we start our investigations with an analysis of the triangulation-based approach by Aichholzer and Aurenhammer. The results obtained motivated us to pursue an approach that involves the generalization of the so-called motorcycle graph from non-degenerate polygons to arbitrary planar straight-line graphs. Using this generalization, we were able to extend the nonprocedural characterization by Cheng and Vigneron to planar straight-line graphs. As a side-product, we obtain an approach to straight skeletons by means of 3D graphics hardware. The main application, however, is a novel wavefront-type algorithm that is (i) suitable for implementation, (ii) efficient in time and space for real-world applications and (iii) operates on arbitrary planar straight-line graphs. The worst-case complexity of our algorithm is by a