It is well-known that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in d-dimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in O(n~2 log n) time using O(n~2) space. Since the lower bound for computing such spanners is Ω(n~2), the time complexity of our algorithm is optimal to within a logarithmic factor.
展开▼
