Bounded-Degree Plane Geometric Spanners in Practice
Bounded-Degree Plane Geometric Spanners in Practice
复制标题
有界度平面几何扳手的实践
DOI：
10.1145/3582497
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Wisnosky, David
中科院分区：
文献类型：
--
作者：
Anderson, Frederick;Ghosh, Anirban;Graham, Matthew;Mougeot, Lucas;Wisnosky, David
自2002年Bose、Gudmundsson和Smid提出构造有界度平面几何扳手的第一个算法以来，有界度平面几何扳手的构造一直是关注的焦点。迄今为止，已经设计了11种算法，在程度和拉伸因子方面进行了各种权衡。我们使用CGAL库在c++中实现了这些复杂的扳手算法，并使用大型合成点集和现实世界的点集对它们进行了实验。我们的实验揭示了它们的实际行为和现实世界的功效。我们通过GitHub分享实现，以供更广泛的使用和未来的研究。我们设计和工程了一个简单实用的算法estimatestrechfactor，它可以估计几何扳手的拉伸因子（获得精确拉伸因子的下界），这是一个具有挑战性的问题，目前还没有实用的算法。在我们的有界度平面几何扳手实验中，我们发现estimatestrechfactor几乎可以精确地估计拉伸因子。此外，它在实践中为本工作中考虑的点集分布提供了线性运行时性能，使其在计算拉伸因子时比基于朴素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, 11 algorithms have been designed with various tradeoffs in degree and stretch-factor. We have implemented these sophisticated spanner 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 design and engineerEstimateStretchFactor, a simple practical algorithm, which 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 found thatEstimateStretchFactorestimated stretch-factors almost precisely. Further, it gave 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.
登录
查看更多内容
正则 ngon 的最小膨胀三角剖分
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
Christian Knauer
通讯作者：
Christian Knauer
单位圆盘图的平面跳跃扳手：更简单、更好
DOI：
--
发表时间：
2019
期刊：
Computational geometry
影响因子：
--
作者：
Ahmad Biniaz
通讯作者：
Ahmad Biniaz
几何T型扳手的实验研究
DOI：
--
发表时间：
2005
期刊：
JEAL
影响因子：
--
作者：
M. Farshi;Joachim Gudmundsson
通讯作者：
Joachim Gudmundsson
构造具有其他稀疏属性的 3 级 Spanner
DOI：
--
发表时间：
1993
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
G. Das;P. Heffernan
通讯作者：
P. Heffernan
DOI：
10.1145/200836.200853
发表时间：
1995-01-01
期刊：
JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY
影响因子：
--
作者：
CALLAHAN, PB;KOSARAJU, SR
通讯作者：
KOSARAJU, SR