论文标题
实践中有限度平面几何跨度
Bounded-degree plane geometric spanners in practice
论文作者
论文摘要
自2002年Bose，Gudmundsson和Smid提出了第一个构造此类跨度的算法以来，有界水平平面几何跨度的构建一直是人们关注的焦点。迄今为止，已经设计了11种算法，具有各种权衡的程度和伸展因素。我们已经使用CGAL库在C ++中实现了这些复杂的算法，并使用大型合成和现实世界进行了实验。我们的实验揭示了他们的实际行为和现实世界的功效。我们通过Github共享实施方式，以进行更广泛的用途和未来的研究。 我们提出了一种简单的实用算法，称为appxstrotchfactor，可以估算几何跨度的拉伸因子（在确切的拉伸因子上获得下限） - 这是一个具有挑战性的问题，尚无实践算法。在我们对有界水平平面几何跨度的实验中，我们发现AppXstrotchFactor几乎精确地估计了伸展因子。此外，它在这项工作中考虑的点集分布中提供了线性运行时性能，这使得它比基于天真的Dijkstra的算法要快得多，以计算拉伸因子
The construction of bounded-degree plane geometric spanners has been a focus of interest since 2002 when Bose, Gudmundsson, and Smid proposed the first algorithm to construct such spanners. To date, eleven algorithms have been designed with various trade-offs in degree and stretch factor. We have implemented these sophisticated algorithms in C++ using the CGAL library and experimented with them using large synthetic and real-world pointsets. Our experiments have revealed their practical behavior and real-world efficacy. We share the implementations via GitHub for broader uses and future research. We present a simple practical algorithm, named AppxStretchFactor, that can estimate stretch factors (obtains lower bounds on the exact stretch factors) of geometric spanners - a challenging problem for which no practical algorithm is known yet. In our experiments with bounded-degree plane geometric spanners, we find that AppxStretchFactor estimates stretch factors almost precisely. Further, it gives linear runtime performance in practice for the pointset distributions considered in this work, making it much faster than the naive Dijkstra-based algorithm for calculating stretch factors
