这是本文档旧的修订版！

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