In order to make straight skeletons applicable in practice we seek an algorithm which is (i) easy to implement and (ii)exhibits an actual runtime that is relatively close to linear in the input size. Fortune started his introduction [For00] to the 27th volume of Algorithmica with the following words:

It is notoriously difficult to obtain a practical implementation of an abstractly described geometric algorithm. This difficulty arises in part from the concep- tual complexity of many geometric algorithms, which often use sophisticated data structures or require other complex algorithms as subroutines. The diffi- culty alsoarises because many algorithms are designed and described to achieve good asymptotic behavior in the worst case, ignoring behavior in more realistic situations.

In this chapter we present a novel straight-skeleton algorithm which is (i)easy to imple- ment, (ii)exhibits a runtime that is close to linear in practice, (iii) accepts planar straight-line graphs as input, and (iv)has a lower worst-case runtime complexity than the triangulation- based algorithm by Aichholzer and Aurenhammer [AA98].

We start with an investigation of the number of flip events that occur for the algorithm by Aichholzer and Aurenhammer [AA98] in Section 2.2. We first show a few results regarding the gap between (n2) and O® for the worst-case number of flip events and prove that we can exploit Steiner triangulations in order to completely avoid all flip events. This insight motivates an algorithm for straight skeletons of non-degenerate polygons that is based on motorcycle graphs, see Section 2.3. In order to generalize this algorithm to arbitrary planar straight-line graphs we introduce a generalization of the motorcyclegraph in Section 2.4 and present an extension of our straight-skeleton algorithm in Section 2.5. Extensive runtime experiments in Section 2.5.4 reveal that our straight-skeleton implementation BoNE exhibits an actual runtime consumption of O(n log n) in practice. Most results in the Sections 2.2 to 2.5 have been presented in the following publications:

[HH10b] S. Huber and M. Held. Straight Skeletons and their Relation to Triangula- tions. In Proc. 26th Europ. Workshop Comput. Geom., pages 189-192, Dortmund, Ger- many, Mar 2010

[HH10a]S. Huber and M. Held. Computing Straight Skeletons of Planar Straight-Line Graphs Based on Motorcycle Graphs. In Proc. 22nd Canad. Conf. Comput. Geom. (CCCG 2010), pages 187-190， Winnipeg, Canada, Aug 2010

[HH11c]S. Huber and M. Held. Theoretical and Practical Results on Straight Skeletons of Planar Straight-Line Graphs. In Proc. 27th Annu. ACM Sympos. Comput. Geom., Paris, France, to be published 2011

为了使直线骨架在实践中适用，我们寻求一种算法，该算法 （i） 易于实现，并且 （ii） 表现出在输入大小上相对接近线性的实际运行时。Fortune 在介绍 [For00] 的 Algorithmica 第 27 卷时说了以下话：

众所周知，很难获得抽象描述的几何算法的实际实现。这种困难部分源于许多几何算法的复杂性，这些算法通常使用复杂的数据结构或需要其他复杂的算法作为子程序。之所以出现这种困难，还在于许多算法的设计和描述是为了在最坏的情况下实现良好的渐近行为，而忽略了更现实情况下的行为。

在本章中，我们提出了一种新颖的直线骨架算法，它 （i） 易于实现，（ii） 在实践中表现出接近线性的运行时间，（iii） 接受平面直线图作为输入，并且 （iv） 与 Aichholzer 和 Aurenhammer [AA98] 的基于三角测量的算法相比，最坏情况下的运行时复杂度更低。

我们首先在第 2.2 节中研究了 Aichholzer 和 Aurenhammer [AA98] 为该算法发生的翻转事件的数量。我们首先展示了一些关于最坏情况下翻转事件数量的 （n2） 和 O® 之间间隙的结果，并证明我们可以利用 Steiner 三角剖分来完全避免所有翻转事件。这一见解激发了一种基于摩托车图的非简并多边形直线骨架算法，参见第 2.3 节。为了将该算法推广到任意平面直线图，我们在第 2.4 节中介绍了摩托车图的推广，并在第 2.5 节中介绍了直线骨架算法的扩展。第 2.5.4 节中的大量运行时实验表明，我们的直线框架实现 BoNE 在实践中表现出 O（n log n） 的实际运行时消耗。第 2.2 至 2.5 节中的大多数结果已在以下出版物中介绍：

[HH10b] S. Huber 和 M. Held。直线骨架及其与三角测量的关系。第 26 届欧洲会议记录。研讨会计算。Geom.，第 189-192 页，德国多特蒙德，2010 年 3 月

[HH10a]S. Huber 和 M. Held。基于摩托车图计算平面直线图的直线骨架。第 22 届加拿大会议论文集。Geom. （CCCG 2010），第 187-190 页，加拿大温尼伯，2010 年 8 月

[HH11c]S. Huber 和 M. Held。平面直线图直线骨架的理论和实践结果。论文集第 27 年。ACM 研讨会。计算。Geom.，法国巴黎，将于 2011 年出版

This suggests that we can obtain an algorithm for computing straight skeletons by by employing the motorcycle graph during the wavefront propagation process. In contrast to the former sections we do not consider a triangulation but maintain the intersection points of M with the wave front and call them Steiner vertices. The following types of events occur, see Fig. 5: (i) edge event: two neighboring convex vertices in a convex part of P meet; (ii) split event: a reflex vertex meets its corresponding Steiner vertex; (iii) switch event: a convex vertex meets a Steiner event and hence the convex vertex migrates to a different convex part of P ; (iv) start event: a reflex vertex or a (moving) Steiner vertex meets a (resting) Steiner vertex, which is the endpoint of a different trace and has to start moving. Note that only neighboring2 vertices meet in the propagation process since the motorcycle graph decomposes the shrinking polygon P at any time into convex parts.

这表明我们可以通过在波前传播过程中使用摩托车图来获得计算直线骨架的算法。与前面的章节相反，我们不考虑三角剖分，而是保持M与波前的交点，并称它们为斯坦纳顶点。以下类型的事件会发生，参见图5：（i）边事件：P的凸部分的两个相邻凸顶点相遇；（ii）分裂事件：一个凹顶点与其对应的斯坦纳顶点相遇；（iii）切换事件：一个凸顶点遇到一个斯坦纳事件，因此该凸顶点迁移到P的不同凸部分；（iv）启动事件：一个凹顶点或一个（移动的）斯坦纳顶点遇到一个（静止的）斯坦纳顶点，该顶点是不同轨迹的端点，必须开始移动。请注意，只有相邻的2个顶点在传播过程中相遇，因为摩托车图在任何时候都会将收缩的多边形P分解为凸部分。

This is easy to see since reflex angles at reflex vertices of W(G, t) are split by (parts of) motorcycle traces accordingly. In particular, for t = 0, the lemma implies that G + M(G) induces a tessellation of the plane into (possibly unbounded) convex faces. A consequence of the lemma is that during the propagation of W∗(G, t) only adjacent vertices can meet.

这很容易理解，因为W(G, t)的反射顶点的反射角被摩托车轨迹（的一部分）相应地分割。特别地，对于t = 0，该引理意味着 G + M(G)将平面划分为（可能无界的）凸面。该引理的一个结果是，在W∗(G, t)的传播过程中，只有相邻的顶点才能相遇。