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{sup}2 log n) time using O(n{sup}2) space. Since the lower bound for computing such spanners is Ω(n{sup}2), the time complexity of our algorithm is optimal to within a logarithmic factor.
展开▼
