Computing the Greedy Spanner in Near-Quadratic Time
The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in O(n(2) log n) time. Since computing the greedy spanner has an Omega(n(2)) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.
spanner greedy algorithm doubling dimension dilation stretch factor