Improving Space and Time Complexity of the Gap-Greedy Spanner Algorithm

Improving Space and Time Complexity of the Gap-Greedy Spanner Algorithm

Abstract

Let S be a set of n points in and G be a geometric graph with vertex set S. For a fixed real number t 1, G is called a t-spanner of S if, for all pairs of vertices u, v S, the shortest path in G between u and v is no longer than t|uv|, where |uv| is the Euclidean distance between u and v. In this paper, we present an algorithm to construct the gap-greedy spanner that takes O n time and O n space, and another variant of this algorithm that takes O n time and O n space. We also improve the (theoretical) dilation of the gap-greedy spanner. Moreover, we present some other O n time algorithms to construct the gap-greedy spanner and compare their time complexity with the gap-greedy algorithm in practice. Furthermore, we experimentally compare the running time and some geometric properties of the gap-greedy spanner with the greedy spanner.

References