Assume we are given a simple1 polygon in the plane which constitutes the outer walls of a house in a ground plan. How can we automatically build a roof such that all faces of the roof have equal slope and no rain drop gets caught in a sink? Assume we are given a polygon with holes2 which is to be milled out with a numerically controlled machine (NC machine). How do we compute so-called offset curves of the input such that sharp vertices of the input remain sharp for the offset curve?3 Assume we are given a simple polygon drawn on a paper. How can we determine a series of complete folds of the paper and a subsequent single cut through the folded paper such that one of the resulting paper pieces has the shape of the polygon? These three problems share a common feature: they can be solved using the straight skeleton.

假设我们有一个平面上的简单多边形simple1，它构成了房屋地基平面的外墙。如何自动构建一个屋顶，使得屋顶的所有面都具有相同的坡度，并且没有雨滴会被困在凹陷处？假设我们有一个带孔的多边形holes2，需要用数控机床（NC机床）铣削出来。我们如何计算输入的所谓偏移曲线，使得输入的尖锐顶点对于偏移曲线保持尖锐？3假设我们有一个画在纸上的简单多边形。我们如何确定一系列完整的纸张折叠方式，以及随后通过折叠纸张的单次切割，使得其中一个产生的纸片具有该多边形的形状？这三个问题有一个共同的特点：它们可以使用直线骨架来解决。

Roughly speaking, the straight skeleton of a simple polygon P is a tree-like skeleton structure that is similar to Voronoi diagrams of polygons, but consists of straight-line segments only. The definition of the straight skeleton is based on the so-called wavefront propagation process. In a nutshell, the straight skeleton of P consists of the set of points that are traced out by the vertices of P when the edges of P shrink inwards in a self-parallel manner and with constant speed. During this propagation process, some edges may vanish and the polygon may successively disintegrate into multiple parts, see Figure 1. Straight skeletons of simple polygons were introduced by Aichholzer et al. [AAAG95] and were subsequently generalized to planar straight-line graphs4 by Aichholzer and Aurenhammer [AA96] about one and a half decades ago. Similar to Voronoi diagrams, straight skeletons possess a heterogeneous plenitude of applications and many of them appeared just in the past decade. The list of applications includes

粗略地说，简单多边形P的直线骨架是一种类似于多边形Voronoi图的树状骨架结构，但仅由直线段组成。直线骨架的定义基于所谓的波前传播过程。简而言之，P的直线骨架由P的顶点在P的边以自平行的方式和恒定速度向内收缩时所描绘出的一组点组成。在此传播过程中，一些边可能会消失，并且多边形可能会连续分解为多个部分，参见图[NT4]1。简单多边形的直线骨架由Aichholzer等人[AAAG95]提出，随后由Aichholzer和Aurenhammer在约15年前推广到平面直线图4 [AA96]。与Voronoi图类似，直线骨架具有广泛的异构应用，其中许多应用仅在过去十年中出现。应用列表包括

1. the computation of mitered offset curves and motion planning in computer-aided design and computer-aided manufacturing (CAD/CAM) [PC03];
2. 计算机辅助设计与计算机辅助制造（CAD/CAM）中斜接偏移曲线的计算和运动规划[PC03]；
3. computing the quickest walking paths in a Manhattan-style city with a fast public transit by means of the city Voronoi diagram; computing critical areas in VLSI circuit models [AAP04, Pap98];
4. [通过城市Voronoi图计算曼哈顿式城市中具有快速公共交通的最快步行路径；计算VLSI电路模型中的关键区域 [AAP04, Pap98]
5. automatic roof generation, terrain modeling and area collapsing within maps in geographical information systems (GIS) [AAAG95, AA96, LD03, MWH+06, KW11, Hav05, HS08];
6. 地理信息系统 (GIS) 中地图内的自动屋顶生成、地形建模和区域坍塌 [AAAG95, AA96, LD03, MWH+06, KW11, Hav05, HS08];
7. and polygon decompositions [TV04b].
8. 和多边形分解 [TV04b]。
9. solving fold-and-cut problems, computing hinged dissections of polyhedra and related problems in the field of mathematical origami [DO07, DDL98, DDM00, DDLS05];
10. 解决折叠和剪切问题，计算多面体的铰接解剖以及数学折纸领域中的相关问题 [DO07, DDL98, DDM00, DDLS05]
11. shape reconstruction and interpolation of contour lines in three-dimensional space [OPC96, BGLSS04];
12. 三维空间中轮廓线的形状重构和插值 [OPC96, BGLSS04];
13. Some of these applications are genuine to straight skeletons, like fold-and-cut problems or automatic roof construction. Other applications are inherited from generalizations of Voronoi diagrams, like many problems in the fields of CAD/CAM, VLSI and GIS.
14. 这些应用中有一些是直线骨架所特有的，例如折叠切割问题或自动屋顶建造。其他的应用则继承自Voronoi图的推广，例如CAD/CAM、VLSI和GIS等领域的许多问题。

In contrast to the large number of applications, we perceive a gap between available algorithms and implementations on the one hand and the best known lower time bound on the other hand. At the moment, the best known lower time bound for the computation of straight skeletons is Ω(n) for an n-vertex polygon and Ω(n log n) for an n-vertex planar straight line graph. However, the currently fastest algorithm for arbitrary polygons and planar straight-line graphs is due to Eppstein and Erickson [EE99] and has a theoretical worst-case time complexity of O(n17/11+ϵ), where ϵ > 0 is an arbitrary small number. The only straight-skeleton implementation available is shipped with the CGAL library [CGA] and was implemented by Cacciola [Cac04]. However, our experiments revealed that the underlying algorithm needs $O(n^2 log n)$ time and $O(n^2)$ space for practical input data.

与大量的应用形成对比的是，我们发现现有算法和实现一方面与已知的最佳时间下界之间存在差距。目前，对于一个n顶点多边形，计算直线骨架的最佳已知时间下界是Ω(n)；对于一个n顶点平面直线图，最佳已知时间下界是Ω(n log n)。然而，目前针对任意多边形和平面直线图的最快算法是由Eppstein和Erickson提出的[EE99]，其理论最坏情况时间复杂度为$O(n^{17/11+ϵ})$，其中ε > 0是一个任意小的数。唯一可用的直线骨架实现是CGAL库[CGA]附带的，由Cacciola实现[Cac04]。然而，我们的实验表明，对于实际的输入数据，底层算法需要$O(n^2 log n)$的时间和$O(n^2)$的空间。

This thesis deals with theoretical properties and the practical computation of straight skeletons and motorcycle graphs. The goal is to develop a practice-minded straight-skeleton algorithm, which accepts arbitrary planar straight-line graphs as input, is efficient in time and space and easy to implement.

本论文探讨了直线骨架和摩托车图的理论性质和实际计算。目标是开发一种注重实践的直线骨架算法，该算法接受任意平面直线图作为输入，在时间和空间上都高效且易于实现。