论文标题
覆盖的定向的伏诺伊图和1-Steiner树问题
Overlaid oriented Voronoi diagrams and the 1-Steiner tree problem
论文作者
论文摘要
已知覆盖的定向的伏洛尼图（OOVD）为建造最佳欧几里得$ 1 $ steiner树提供了有用的数据。利用OOVD的施工方法的理论时间复杂性为$ O（n^2）$，但是从未进行过计算研究，并且以前尚未实施针对OOVD的强大构造。 在本文中，我们概述了使用计算几何算法库（CGAL）中的工具构建OOVD的数值稳定实现，并在随机点集上测试其性能。然后，我们研究了OOVD数据与幼稚方法相比，OOVD数据对降低$ 1 $ steiner树的复杂性的影响。 1-Steiner算法的主回路的迭代次数直接由OOVD中的面数确定，这对于我们测试的随机输入似乎是线性的。我们还讨论了处理OOVD数据的方法，该数据导致施工时间减少了大约12倍。
Overlaid oriented Voronoi diagrams (OOVDs) are known to provide useful data for the construction of optimal Euclidean $1$-Steiner trees. The theoretical time complexity of construction methods exploiting the OOVD is $O(n^2)$, but a computational study has never been performed, and robust constructions for OOVDs have not previously been implemented. In this paper, we outline a numerically stable implementation for constructing OOVDs using tools from the Computational Geometry Algorithms Library (CGAL), and test its performance on random point sets. We then study the effect that the OOVD data has in reducing the complexity of $1$-Steiner tree construction when compared to a naive approach. The number of iterations of the main loop of the 1-Steiner algorithm is directly determined by the number of faces in the OOVD, and this appears to be linear for the random inputs we tested. We also discuss methods for processing the OOVD data that lead to a reduction in construction time by roughly a factor of 12.
