Let G be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t>1, a spanning subgraph G′ of G is said to be a t-spanner, or simply a spanner, if for any pair of nodes p, q in G there exists a t-path in G′, i.e., a path between p and q whose length is at most t times their distance in G. Gap-greedy spanner, proposed by Arya and Smid, is a light weight and bounded degree spanner in which a pair of points p,q is guaranteed to have a t-path, if there exists at least one edge with some special criteria in the spanner. Existing algorithms for computing the gap-greedy spanner determine the existence of such an edge for each pair of points by examining the edges of the spanner, which takes O(n) time, however in this paper, we have presented a method by which this task can be done in O(1) time. Using the proposed method and well-separated pair decomposition, we have proposed a linear-space algorithm that can compute the gap-greedy spanner in O(n2) time. How to use the well-separated pair decomposition to compute this spanner was proposed by Bakhshesh and Farshi, however using an example, we have shown that one of the algorithms they have proposed for this purpose is incorrect. We have performed various experiments to measure the duration and amount of memory used by the algorithms for computing this spanner. The results of these experiments showed that the proposed method, without a significant effect on the amount of memory consumed compared to previous algorithms, leads to a significant acceleration in the construction time of this spanner.

Keywords