Consider a set of points on the plane and a weighted geometric network where the weight of each is equal to the Euclidean distance between the endpoints of the edge (). Given a constant , a spanning subgraph of is said to be a -spanner, or simply a spanner, if for any pair of nodes in there exists a path between and whose length is at most times their distance in . Gap greedy spanner, proposed by Arya and Smid, is a light weight and bounded degree spanner in which a pair of points is guaranteed to have a -path, if there exists at least one edge with some special criteria in the spanner. In our previous work, we introduced an algorithm with linear space complexity that takes time to construct this spanner, utilizing well-separated pair decomposition. However, empirical results from experiments revealed that the performance of the algorithm is significantly dependent on the number of well-separated pairs obtained. In this paper, to mitigate the construction dependency on the number of well-separated pairs, we confine its usage to the processing of a small subset of point pairs. This limitation stems from the observation that a substantial portion of the edges in this spanner have small sizes. Consequently, we first empirically highlight the prevalence of the small edge size characteristic within the spanner. Subsequently, we propose an algorithm for computing this spanner that, based on the experimental results, exhibits a higher computational speed in generating the gap greedy spanner in most cases.

Keywords