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

Let S be a set of n points in Rd 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.