Computing straight skeletons of planar straight-line graphs based on motorcycle graphs
Computing straight skeletons of planar straight-line graphs based on motorcycle graphs
复制标题
基于摩托车图的平面直线图直骨架计算
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Held
中科院分区：
文献类型：
--
作者：
S. Huber;M. Held
我们给出了一个计算平面直线图的直骨架的简单算法。我们利用摩托车图和直线骨架之间的关系，提出了一种波前传播算法，避免了对下一个分裂事件进行昂贵的搜索。我们的算法保持了Aichholzer和AurenHammer基于三角剖分的算法的简单性，但具有更好的最坏情况下O(N2logn)的复杂度。实现的初步实验表明，实际运行时间可以达到O(N Logn)。
We present a simple algorithm for computing straight skeletons of planar straight-line graphs. We exploit the relation between motorcycle graphs and straight skeletons, and introduce a wavefront-propagation algorithm that circumvents the expensive search for the next split event. Our algorithm maintains the simplicity of the triangulation-based algorithm by Aichholzer and Aurenhammer but has a better worst-case complexity of O(n 2 logn). Preliminary experiments with our implementation demonstrate that an actual runtime of O(n logn) can be expected in practice.