id: 05791715
dt: j
an: 05791715
au: Bose, Prosenjit; Carmi, Paz; Farshi, Mohammad; Maheshwari, Anil; Smid,
    Michiel
ti: Computing the greedy spanner in near-quadratic time.
so: Algorithmica 58, No. 3, 711-729 (2010).
py: 2010
pu: Springer-Verlag New York Inc., New York
la: EN
cc: 
ut: Spanner; Dilation; Stretch factor; Greedy algorithm; Doubling dimension
ci: 
li: doi:10.1007/s00453-009-9293-4
ab: Summary: 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 $ {\text {O}}(n^{2}\log 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.
rv: