Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
复制标题
DOI：
10.1137/s0097539700382947
复制
发表时间：
2002-05
期刊：
影响因子：
--
通讯作者：
Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
中科院分区：
文献类型：
--
作者：
Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
给定在$\mathbb{R}^d$中的$n$个点的集合$V$以及一个实常数$t > 1$，我们提出了第一个$O(n\log n)$时间的算法来计算$V$上的一个几何$t$-生成树。$V$上的一个几何$t$-生成树是一个连通图$G=(V,E)$，其边的权重等于端点之间的欧几里得距离，并且具有这样的性质：对于所有的$u,v\in V$，$u$和$v$在$G$中的距离至多是$u$和$v$之间欧几里得距离的$t$倍。该算法输出的生成树有$O(n)$条边且权重为$O(1)\cdot wt(MST)$，并且它的度由一个常数界定。
Given a set V of n points in $\IR^d$ and a real constant t>1, we present the first O(nlog n)-time algorithm to compute a geometric t-spanner on V. A geometric t-spanner on V is a connected graph G = (V,E) with edge weights equal to the Euclidean distances between the endpoints, and with the property that, for all $u,v\in V$, the distance between u and v in G is at most t times the Euclidean distance between u and v. The spanner output by the algorithm has O(n) edges and weight $O(1)\cdot wt(MST)$, and its degree is bounded by a constant.