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 2log n) time. Since computing the greedy spanner has an Ω(n 2) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.

Additional Metadata
Keywords Dilation, Doubling dimension, Greedy algorithm, Spanner, Stretch factor
Persistent URL dx.doi.org/10.1007/s00453-009-9293-4
Journal Algorithmica
Citation
Bose, P, Carmi, P. (Paz), Farshi, M. (Mohammad), Maheshwari, A, & Smid, M. (2010). Computing the greedy spanner in near-quadratic time. Algorithmica, 58(3), 711–729. doi:10.1007/s00453-009-9293-4