Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan · SIAM Journal on Computing · 2002
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.