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.

, , , ,
doi.org/10.1007/s00453-009-9293-4
Algorithmica
Computational Geometry Lab

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