这是本文档旧的修订版！

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 年出版