The straight skeleton is a geometric structure that is similar to generalized Voronoi diagrams. Straight skeletons were introduced to the field of computational geometry one and a half decades ago. Since then many industrial and academical applications emerged, such as the computation of mitered offset curves, automatic roof construction, solving fold-and-cut problems and the reconstruction of surfaces, to name the most prominent ones. However, there is a significant gap between the most efficient straight-skeleton algorithms and implementations, on one hand, and the best known lower runtime bounds on the other hand. The primary goal of this thesis is the development of an algorithm that is suitable for implementation and efficient in terms of time and space in order to make the advantages of straight skeletons available to real-world applications.

直骨架是一种类似于广义Voronoi图的几何结构。直骨架在十多年前被引入到计算几何领域。自那时以来，涌现了许多工业和学术应用，例如计算斜接偏移曲线、自动屋顶建造、解决折叠切割问题以及表面重建，仅举几个最突出的例子。然而，在最有效的直骨架算法和实现，与已知的最佳运行时下界之间存在显著差距。本论文的主要目标是开发一种适用于实现，并且在时间和空间方面都高效的算法，以便使直骨架的优势能够应用于现实世界的应用。

We start with investigations concerning upper and lower bounds on the number of socalled flip events that occur in the triangulation-based straight-skeleton algorithm by Aichholzer and Aurenhammer. In particular, we prove the existence of Steiner triangulations that are free of flip events. This result motivates a novel straight-skeleton algorithm for non-degenerate simple polygons that is based on the so-called motorcycle graph. In order to extend this algorithm to arbitrary planar straight-line graphs, we carefully generalize the motorcycle graph. This generalization leads to practical and theoretical applications: Firstly, we obtain an extension of the alternative characterization of straight skeletons by Cheng and Vigneron to planar straight-line graphs. Secondly, this characterization motivates a straight-skeleton algorithm that is based on 3D graphics hardware. Thirdly, the generalized motorcycle graph leads to a wavefront-type straight-skeleton algorithm for arbitrary planar straight-line graphs. Our algorithm is easy to implement, has a theoretical worstcase time complexity of $O(n^2 log n)$ and operates in $O(n)$ space. Extensive runtime tests with our implementation Bone exhibit an actual runtime of O(n log n) on a database containing more than 13 500 datasets of different characteristics. In practice, this constitutes an improvement of a linear factor in time and space compared to the current state-of-the-art straight-skeleton code, which is shipped with the CGAL library. In particular, Bone performs up to 100 times faster than the current CGAL code on datasets with a few thousand vertices, requires significant less memory and accepts more general input.

我们首先研究由 Aichholzer 和 Aurenhammer 提出的基于三角剖分的直骨架算法中出现的所谓翻转事件的数量的上下界。特别地，我们证明了存在没有翻转事件的斯坦纳三角剖分。这一结果促使我们提出了一种基于所谓摩托车图的非退化简单多边形的新型直骨架算法。为了将此算法扩展到任意平面直线图，我们仔细地推广了摩托车图。这种推广带来了实际和理论应用：首先，我们将 Cheng 和 Vigneron 对直骨架的替代表征扩展到平面直线图。其次，这种表征激发了一种基于 3D 图形硬件的直骨架算法。第三，广义摩托车图产生了一种用于任意平面直线图的波前型直骨架算法。我们的算法易于实现，理论最坏情况时间复杂度为 $O(n^2 log n)$，并在 O(n) 空间中运行。我们使用 Bone 实现的大量运行时测试表明，在一个包含超过 13 500 个不同特征数据集的数据库上，实际运行时为 O(n log n)。在实践中，与 CGAL 库附带的当前最先进的直骨架代码相比，这在时间和空间上都提高了线性因子。特别地，在具有数千个顶点的数据集上，Bone 的执行速度比当前的 CGAL 代码快 100 倍，需要的内存更少，并且接受更通用的输入。

Our straight-skeleton algorithm motivates the investigation of motorcycle graphs and their practical computation. We start with stochastic considerations of the average length of a motorcycles trace. The results obtained motivate a simple yet fast algorithm that employs geometric hashing. Runtime tests with our implementation Moca exhibit an O(n log n) runtime on the vast majority of our datasets. Finally, we revisit the geometric relation of straight skeletons and motorcycle graph. We present an algorithm that constructs planar straight-line graphs whose straight skeleton approximates any given motorcycle graph to an arbitrary precision. This algorithm finally leads to a P-completeness proof for straight skeletons of polygons with holes that is based on the P-completeness of motorcycle graphs.

我们的直线骨架算法激发了对摩托车图及其在实践中计算的研究。我们首先对摩托车轨迹的平均长度进行随机性考虑。所得结果促使我们采用一种简单而快速的算法，该算法采用了几何哈希。我们使用我们的实现Moca进行的运行时测试表明，在我们绝大多数数据集上，运行时复杂度为O(n log n)。最后，我们重新审视直线骨架和摩托车图的几何关系。我们提出了一种算法，该算法构建的平面直线图的直线骨架可以以任意精度逼近任何给定的摩托车图。该算法最终导出了一个关于带孔多边形直线骨架的P-完全性证明，该证明基于摩托车图的P-完全性。

I would like to thank my parents, Stefan and Gabriele, for their unlimited and unconditional support throughout my entire life. Special thanks go to my girlfriend Christina for her constant support and understanding during my doctoral studies.

我要感谢我的父母，Stefan 和 Gabriele，感谢他们在我一生中给予我的无限和无条件的支持。特别感谢我的女朋友 Christina，感谢她在我的博士学习期间给予我的持续支持和理解。

I also thank my supervisor Martin Held for his guidance and his extensive support. Further, I thank my colleagues and co-workers. In particular I thank Gerhard Mitterlechner and Roland Kwitt for their proofreading and valuable discussions.

我还要感谢我的导师马丁·赫尔德（Martin Held）的指导和大力支持。此外，我感谢我的同事和合作者。特别感谢格哈德·米特勒赫纳（Gerhard Mitterlechner）和罗兰·奎特（Roland Kwitt）的校对和宝贵讨论。

Eventually, I thank the Austrian Science Fund (FWF) for supporting this thesis by funding project no. L367-N15.

最后，我感谢奥地利科学基金会（FWF）通过资助项目编号L367-N15来支持本论文。