Experimental study of geometric t-spanners
Experimental study of geometric t-spanners
复制标题
几何T型扳手的实验研究
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Joachim Gudmundsson
中科院分区：
文献类型：
--
作者：
M. Farshi;Joachim Gudmundsson
给定点集的t-空间的构造受到了广泛的关注，特别是从理论的角度。在这篇文章中，我们实验研究的性能和质量的最常见的建设算法的点在欧几里德平面。我们实现了最著名的t-mapping算法，并在许多不同的点集上进行了测试。实验进行了讨论和比较的理论结果，并在几种情况下，我们建议的修改，实施和评估。我们考虑的质量度量是边的数量、权重、最大度、顶点直径和交叉数。这是第一次广泛的比较之间的运行时间的建设算法的t-spectrum和质量的生成spectrum。
The construction of t-spanners of a given point set has received a lot of attention, especially from a theoretical perspective. In this article, we experimentally study the performance and quality of the most common construction algorithms for points in the Euclidean plane. We implemented the most well-known t-spanner algorithms and tested them on a number of different point sets. The experiments are discussed and compared to the theoretical results, and in several cases, we suggest modifications that are implemented and evaluated. The measures of quality that we consider are the number of edges, the weight, the maximum degree, the spanner diameter, and the number of crossings. This is the first time an extensive comparison has been made between the running times of construction algorithms of t-spanners and the quality of the generated spanners.