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 linear factor better than the triangulation-based algorithm. In comparison with the former state-of-the-art implementation, which is shipped with the CGAL library, our C++ code Bone (i) handles more general input, (ii) is by a linear factor faster and (iii) by a linear factor more space efficient. As a result, our code is the first implementation that is able to compute the straight skeleton of datasets comprising up to a few million vertices. In the second part of the thesis we focus on the practical computation of generalized motorcycle graph. We start with stochastic considerations of the mean trace length of random motorcycle graphs. The results motivated a simple algorithm that performs in O(n log n) time on the vast majority of datasets in our database. To the best of our knowledge, our C++ implementation Moca is currently the only competitive motorcycle-graph code available. Finally, we show how to approximate a motorcycle graph using a straight skeleton. Based on these investigations we prove the P-completeness of straight skeletons of polygons with holes.