In this chapter, we start with the definition of straight skeletons, the terrain model and the motorcycle graph in Section 1.2. We continue with a presentation of several applications of straight skeletons in Section 1.3. In Section 1.4, we review known algorithms and implementations of straight skeletons and motorcycle graphs and in Section 1.5, we discuss different approaches by which straight skeletons were generalized.

在本章中，我们首先在第1.2节中给出直线骨架、地形模型和摩托车图的定义。然后，在第1.3节中介绍直线骨架的几个应用。在第1.4节中，我们回顾已知的直线骨架和摩托车图的算法和实现，并在第1.5节中，我们讨论直线骨架推广的不同方法。

Chapter 2 is devoted to the computation of straight skeletons. In Section 2.1, we collect known geometric properties of the straight skeleton and present them along with their proofs in a unified formalism based on the definitions in Section 1.2. In Section 2.2, we analyze the triangulation-based algorithm by Aichholzer and Aurenhammer [AA98]. We prove a few results concerning the lower and upper bounds for the number of the so-called flip events and show that Steiner triangulations exist where no flip events occur.

第2章致力于直线骨架的计算。在第2.1节中，我们收集了直线骨架的已知几何性质，并基于第1.2节中的定义，以统一的形式化方法呈现了这些性质及其证明。在第2.2节中，我们分析了Aichholzer和Aurenhammer [AA98]提出的基于三角剖分的算法。我们证明了一些关于翻转事件数量的上下界的结果，并表明存在没有翻转事件发生的斯坦纳三角剖分。

This insight motivates a novel straight-skeleton algorithm for simple non-degenerate5 polygons that is based on the motorcycle graph in Section 2.3. In order to extend this approach to arbitrary planar straight-line graphs, we carefully generalize the motorcycle graph in Section 2.4. Further, we prove two essential geometric properties for this generalization that are important for our algorithmic approach: (i) the input graph and the motorcycle graph tessellate the plane into convex faces and (ii) the generalized motorcycle graph covers the reflex arcs of the straight skeleton.

这一观察促使我们提出了一种新的针对简单非退化5多边形的直骨架算法，该算法基于第2.3节中的摩托车图。为了将这种方法扩展到任意平面直线图，我们仔细地推广了第2.4节中的摩托车图。此外，我们证明了这种推广的两个重要的几何性质，这些性质对于我们的算法方法至关重要：（i）输入图和摩托车图将平面镶嵌成凸面，以及（ii）广义摩托车图覆盖了直骨架的凹弧。

In addition, the generalized motorcycle graph permits an extension of Cheng and Vigneron’s alternative characterization of straight skeletons to arbitrary planar straight-line graphs. Furthermore, this characterization motivates a straight-skeleton algorithm that employs 3D graphics hardware to approximately compute the straight skeleton.

此外，广义摩托车图允许将 Cheng 和 Vigneron 对直线骨架的另一种表征扩展到任意平面直线图。此外，这种表征激发了一种直线骨架算法，该算法采用 3D 图形硬件来近似计算直线骨架。

In Section 2.5, we present a wavefront-type straight-skeleton algorithm for arbitrary planar straight-line graphs. Our implementation Bone runs in $O(n^2 log n)$ time in the worstcase and uses O(n) space. Experiments exhibit an actual O(n log n) runtime on real-world input. This constitutes a speed-up by a linear factor in time and space compared to the current state-of-the-art straight-skeleton code that is shipped with the CGAL library.

在第2.5节中，我们提出了一种用于任意平面直线图的波前型直线骨架算法。我们的实现Bone在最坏情况下以$O(n2 log n)$的时间运行，并使用O(n)空间。实验表明，在实际输入中，实际运行时间为O(n log n)。与CGAL库附带的当前最先进的直线骨架代码相比，这在时间和空间上构成了一个线性因子的加速。

In Chapter 3 we have a closer look on the motorcycle graph. Our straight-skeleton implementation Bone requires a fast motorcycle graph implementation for practical input. We start our investigations with stochastic considerations of the average trace length in a motorcycle graph in Section 3.2. Motivated by the results we obtained, we present a simple motorcycle graph algorithm, which uses geometric hashing to speed up the computation, see Section 3.3. Runtime tests show an actual runtime of O(n log n) on practical input for our implementation Moca.

在第3章中，我们将更仔细地研究摩托车图。我们的直线骨架实现Bone需要一个快速的摩托车图实现来处理实际输入。我们从第3.2节中摩托车图中平均轨迹长度的随机考虑开始我们的研究。受到我们获得的结果的启发，我们提出了一个简单的摩托车图算法，该算法使用几何哈希来加速计算，见第3.3节。运行时测试表明，对于我们的Moca实现，在实际输入上实际运行时间为O(n log n)。

In Section 3.4, we further investigate the geometric relation between the straight skeleton and the motorcycle graph. We first show how to construct a planar straight-line graph whose straight skeleton approximates the motorcycle graph up to any given precision. Further, we present a simple algorithm that computes the motorcycle graph using the straight skeleton. This algorithm finally leads to a LOGSPACE-reduction of the motorcycle graph problem to the straight skeleton problem, which proves the P-completeness of straight skeletons of polygons with holes based on the P-completeness of the motorcycle graph.

在第3.4节中，我们将进一步研究直线骨架和摩托车图之间的几何关系。我们首先展示如何构造一个平面直线图，其直线骨架以任何给定的精度逼近摩托车图。更进一步，我们提出了一个使用直线骨架计算摩托车图的简单算法。该算法最终将摩托车图问题LOGSPACE归约到直线骨架问题，这证明了基于摩托车图的P完全性，带孔多边形的直线骨架的P完全性。