To the best of our knowledge, the currently best known lower bound to compute the straight skeleton of a simple polygon with $n$ vertices is Ω(n). In the convex case a simulation of the propagating wavefront gives us an almost optimal algorithm using O(n log n) time, see Section 1.4.2.1. For the more general case of monotone polygons, Das et al. [DMN+10] presented an O(n log n) algorithm.

据我们所知，目前计算具有n个顶点的简单多边形的直线骨架的已知下限是 Ω（n）。 在凸情况下，传播波前的模拟为我们提供了使用 O（n log n） 时间的几乎最佳算法，参见第 1.4.2.1 节。对于更一般的单调多边形情况，Das 等人 [DMN+10]提出了一种 O（n log n） 算法。

However, for arbitrary simple polygons, no algorithm that is even reasonably close to linear is known. Currently, the fastest algorithm is due to Eppstein and Erickson [EE99] with a worst-case runtime of O(n17/11+ϵ). This poses a high contrast to the situation for Voronoi diagrams, for which Chin and Snoeyink [CSW99] presented an optimal linear-time algorithm.

然而，对于任意简单多边形，甚至没有相当接近线性的算法是已知的。 目前，最快的算法是由于 Eppstein 和 Erickson [EE99]，最坏情况下的运行时间为 O（n17/11+ε）。这与 Voronoi 图的情况形成了高度对比，Chin 和 Snoeyink [CSW99] 提出了一种最佳线性时间算法。

Note that in the convex case the Voronoi diagram and the straight skeleton are coinciding and the algorithm by Chin and Snoeyink solves the straight-skeleton problem in optimal time as well. However, for convex polygons also a simpler Voronoi algorithm is known due to Aggarwal et al. [AGSS87].

请注意，在凸情况下，Voronoi 图和直线骨架是重合的，并且 Chin 和 Snoeyink 的算法也在最佳时间内解决了直线骨架问题。然而，对于凸多边形，由于 Aggarwal 等[AGSS87]，也已知了一种更简单的 Voronoi 算法。据我们所知，目前计算具有n个顶点的简单多边形的直线骨架的已知最佳下界是Ω(n)。在凸多边形的情况下，模拟传播波前为我们提供了一个使用O(n log n)时间的几乎最优的算法，参见第1.4.2.1节。对于更一般的单调多边形的情况，Das等人[DMN+10]提出了一个O(n log n)算法。然而，对于任意简单多边形，目前还没有已知算法能够合理地接近线性时间复杂度。目前，最快的算法是Eppstein和Erickson提出的[EE99]，其最坏情况下的运行时间为O(n17/11+ϵ)。这与Voronoi图的情况形成了鲜明对比，Chin和Snoeyink [CSW99]提出了一个最优的线性时间算法。请注意，在凸多边形的情况下，Voronoi图和直线骨架是重合的，Chin和Snoeyink的算法也以最佳时间解决了直线骨架问题。然而，对于凸多边形，Aggarwal等人[AGSS87]也提出了一个更简单的Voronoi算法。

For planar straight-line graphs and for polygons with holes, the best known lower bound is Ω(n log n). This is easy to see, since we can simply reduce the sorting problem to straight skeletons. Assume n distinct natural numbers a1, . . . , an are given, which have to be sorted.

对于平面直线图和带孔的多边形，最著名的下限是 Ω（n log n）。 这很容易看出，因为我们可以简单地将排序问题简化为直线骨架。 假设 给出 n 个不同的自然数 a1， . . . ， an 必须对其进行排序。

For any $a_k$, we place a small equilateral triangle that is hinged with its top vertex at the coordinates (ak, 0). The length of the edges of the triangles are considered to be less than 1, say 0.9. Then we put a box around the triangles such that the top vertices of the box have small y -coordinates, say 0.1. The box and the triangles form a simple polygon P with holes with 3n + 4 vertices and can be constructed in O(n) time.

对于任何 k，我们放置一个小的等边三角形，该三角形的顶部顶点在坐标 （ak， 0） 处铰接。 三角形边的长度被认为小于 1，比如 0.9。然后我们在三角形周围放置一个盒子，使盒子的顶部顶点具有较小的 y 坐标，例如 0.1。方框和三角形形成一个简单的多边形 P，其孔具有 3n + 4 个顶点，可以在 O（n） 时间内构造。

After computing S (P) we consider the face f (e) of the top edge e of P that is within P. It is easy to see that the nodes that appear as reflex vertices of f (e) correspond to the input a1, . . . , an and occur in sorted order along the x-axis, see Figure 10.

计算完 S （P） 后， 我们考虑 P 的顶边 e 的面 f （e） 在 P 内。很容易看出，作为 f （e） 的反射顶点出现的节点对应于输入 a1， . . . ， an 并沿 x 轴按排序顺序出现，见图 10。

A simple traverse of f (e) gives us the sorted sequence in linear time. f （e） 的简单遍历为我们提供了线性时间内的排序序列。