In this paper we give a new, efficient algorithm for computing curve skeletons, based on local separators. Our efficiency stems from a multilevel approach, where we solve small problems across levels of detail and combine these in order to quickly obtain a skeleton. We do this in a highly modular fashion, ensuring complete flexibility in adapting the algorithm for specific types of input or for otherwise targeting specific applications. Separator based skeletonization was first proposed by B{\ae}rentzen and Rotenberg in [ACM Tran. Graphics'21], showing high quality output at the cost of running times which become prohibitive for large inputs. Our new approach retains the high quality output, and applicability to any spatially embedded graph, while being orders of magnitude faster for all practical purposes. We test our skeletonization algorithm for efficiency and quality in practice, comparing it to local separator skeletonization on the University of Groningen Skeletonization Benchmark [Telea'16].
翻译:在本文中,我们以本地分隔器为基础,为计算曲线骨骼提供了一种新的高效算法。我们的效率来自多层次的方法,我们解决了不同细节层次的小问题,并将这些问题结合起来,以便迅速获得骨骼。我们以高度模块化的方式这样做,确保在调整特定输入类型或针对特定应用的算法时完全灵活。基于分离的骨架化首先由B&B 和Rotenberg在[ACM Tran.图形 21]中提出,显示高质量的产出,成本是运行时间,而运行时间对大型投入来说却变得令人望而却步。我们的新方法保留了高质量的输出,并适用于任何空间嵌入的图形,而对于所有实际目的而言,其数量更快。我们测试我们的骨架化算法在实践中的效率和质量,将其与格罗宁根斯克里顿化大学基准[Teea'16]的本地分离骨架化比较。</s>