Constructing Doppelgängers of Greedy Geometric Spanners in Practice

We introduce the notion of $(a,b)$-doppelgänger. A $t$-spanner $H$ on a point set $P$ is a $(a,b)$-doppelgänger of the greedy spanner $G$ on $P$, if its average degree and lightness do not exceed those of $G$ by more than additive constants $a$ and $b$, respectively. Average degree and lightness are two central measures of spanner quality, and spanners with similar values for these metrics tend to be structurally similar. Thus, smaller values of $a$ and $b$ indicate better doppelgängers. Such doppelgängers are especially appealing to practitioners when they can be constructed significantly faster than the greedy spanner itself. The term “approximation” has not been used in this work intentionally, as the Approximate-Greedy [19] algorithm claims to generate spanners that are approximations of greedy spanners, but, in reality, they are structurally very different from the actual greedy spanners (also, see Table 1).

Motivated by the lack of fast practical algorithm to generate $(a,b)$-doppelgängers of greedy spanners for low values of $a$ and $b$, we design and engineer $\mathrm{\Theta }$-Greedy, a new spanner construction algorithm, based on $\mathrm{\Theta }$-Graph. We found $\mathrm{\Theta }$-Greedy to be considerably faster than our closest competitor Bucketing, and always produced high quality doppelgängers in our experiments. In our experiments, both $a$ and $b$ never exceeded $0.1$. To our knowledge, no other known algorithm can achieve this while being fast and scalable in practice. See Figure 2 for a visual comparison between $\mathrm{\Theta }$-Greedy and Bucketing.

We use the $\mathrm{\Theta }$-Graph as a seed spanner since it can be constructed fast in $O(n\log n)$ time and, as seen in Table 1, excluding Fast-Sparse-Spanner (not guaranteed to produce $t$-spanners), $\mathrm{\Theta }$-Graphs have the lowest average degree and thus the lowest number of edges. We consider its edges by length and place them greedily, akin to Path-Greedy. Finally, we find point pairs that do not have $t$-paths between them using a quad tree-based approach. For every such point pair, we establish a $t$-path by placing edges carefully. Our algorithm can leverage multiple cores for speedup.

$\mathrm{\Theta }$-Greedy is designed as an engineering solution to a long-standing practical bottleneck in geometric spanner construction rather than as a theoretical breakthrough. While its worst-case complexity is $O(n^3\log n)$, the algorithm consistently exhibits near-quadratic scaling in practice and uses linear space, enabling it to handle million-point datasets efficiently. It leverages heuristic path checks and shortcut caching to achieve massive speedups, up to $\approx 147$x faster than Bucketing, while producing spanners that are structurally almost indistinguishable from true greedy spanners in terms of degree and lightness. The focus of $\mathrm{\Theta }$-Greedy is on simplicity, scalability, and reproducibility for real-world geometric networks, not on improving asymptotic bounds.

A region quad tree is a hierarchical spatial data structure that recursively partitions a two-dimensional region into four congruent quadrants until each subregion is homogeneous or its size falls below a specified threshold $\mathrm{\ell }$, the maximum leaf size. The root node represents the entire region, and each internal node corresponds to a square subdivided into four child quadrants. A $\mathrm{\Theta }$-Graph [28] is a geometric spanner constructed by dividing the plane around each point into $k$ equal-angle cones and connecting the point to the vertex in each cone that minimizes the distance projected onto the cone’s bisector. The constructed geometric graph is a $t$-spanner if $k=\max (9,\frac{2\pi }{\mathrm{\Theta }})$, where $\mathrm{\Theta }=\frac{\arcsin \left(1-\frac{1}{t^2}\right)}{2}$. $\mathrm{\Theta }$-Graph can be constructed in $O(n\log n)$ time [28].

The algorithm begins by inserting the edges of a minimum spanning tree $M$ into $H$. Since $M$ is connected and contains exactly $n-1$ edges, $H$ is connected after Step 1. In Step 2, we place $O(n)$ edges since the size of $G_{\mathrm{\Theta }}$ is $O(n)$, for fixed $t$. Step 3 introduces $O(n)$ edges as $\mathrm{\ell }$ is a constant. We insert at most $\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{2}\right)=O(1)$ edges within each leaf of $T$, and since $T$ has $O(n)$ leaves, the total number of edges added is $O(n)$. If Step 4 places at most $n$ edges, then clearly, $H$ has $O(n)$ edges.

Now, let us assume that the number of edges placed in Step 4 exceeds $n$ (possibly $\omega (n)$). In what follows, we argue that in such a scenario, Step 5 places $O(n)$ edges, thereby proving our sparsity claim for $H$.

Let $u$ be any vertex of $H$. We claim that the number of edges placed in Step 5, that are incident on $u$, is at most $\lceil 2\pi /\alpha \rceil$, such that $\alpha$ satisfies the inequality, $\cos \alpha +t\sin \alpha \le t$. Assume, for contradiction, that two edges $\{u,v\}$ and $\{u,w\}$ are added in Step 5, where $|uv|\le |uw|$, and both lie in the same cone (with angle $\theta \le \alpha$). Since the edge $\{u,v\}$ was processed first, it is already in the graph when $\{u,w\}$ is considered. For the edge $\{u,w\}$ to be prevented from insertion into $H$, the path $P_{u,w}$ going through $v$ must provide a $t$-path in $H$: $|P_{u,w}|\le t\cdot |uw|$.

We analyze the worst-case geometric configuration where $v$ and $w$ are located on the two distinct bounding rays of the cone, maximizing the distance $|vw|$ for angle $\alpha$. Refer to Figure 3. An upper bound on $|P_{u,w}|$ can be given by the distance projected onto the ray containing $v$ plus the stretch factor $t$ applied to the orthogonal component: $|P_{u,w}|\le |uw|\cos \alpha +t\cdot |uw|\sin \alpha$. To prevent the insertion of the edge $\{u,w\}$ in $H$, this upper bound must be less than or equal to $t\cdot |uw|$. Thus, $|uw|\cos \alpha +t\cdot |uw|\sin \alpha \le t\cdot |uw|$. Dividing both sides by $|uw|$, we obtain the necessary angular constraint: $\cos \alpha +t\sin \alpha \le t$. We conclude that there are at most $\lceil 2\pi /\alpha \rceil$ edges placed that are incident on $u$ in $H$. For fixed $t$, $\lceil 2\pi /\alpha \rceil =O(1)$. Hence, Step 5 places $O(n)$ edges.

The $t$-spanner property of $H$ follows directly from Steps 3, 4, 5. In Step 3, we ensure $t$-paths between all point pairs inside every leaf of $T$. In Steps 4 and 5, we ensure $t$-paths between all point pairs $u,v\in P$ where they belong to distinct leaves of $T$.

Thus, $H$ is a $t$-spanner with $O(n)$ edges. $◀$

Step 1 runs in $O(n\log n)$ time as Delaunay triangulations can be constructed in $O(n\log n)$ time (via Voronoi diagram) having at most $3n$ edges and Prim’s algorithm on $O(n)$ edges runs to completion in $O(n\log n)$ time. Next, the construction of the $\mathrm{\Theta }$-Graph $G_{\mathrm{\Theta }}$ takes $O(n\log n)$ time [28]. Also, $|E_{\mathrm{\Theta }}|=O(n)$. For every pair $\{u,v\}\in E_{\mathrm{\Theta }}$, verifying the existence of a $t$-path between $u,v$ takes $O(n)+O(n\log n)=O(n\log n)$ time in the worst-case due to the use of Greedy-Path that runs in $O(n)$ time followed by $A^{\ast }$ that runs in $O(n\log n)$ time in the worst-case. For $O(n)$ pairs in $E_{\mathrm{\Theta }}$, the total time taken is $O(n^2\log n)$. So, Step 2 runs in $O(n^2\log n)$ time. In Step 3, constructing $T$ takes $O(n^2)$ time in the worst case. The remaining part of this step takes $O(n)$ time since the size of every leaf is at most $\mathrm{\ell }=O(1)$. For every leaf of $T$, there are $O(1)$ point pairs not having $t$-paths. For $O(n)$ leaves, there are $O(n)$ such point pairs. Detecting such pairs takes $O(n)$ time since the size of every $H_{\sigma }$ is $O(1)$. Finally, Steps 4 and 5 each take $O(n^3\log n)$ time since there are $O(n^2)$ non-empty leaf pairs of $T$ and for every such pair we spend $O(n\log n)$ time for detecting $t$-paths between $\le {\mathrm{\ell }}^2=O(1)$ point pairs. Thus, the overall worst-case time complexity of $\mathrm{\Theta }$-Greedy is $O(n^3\log n)$.

Although $\mathrm{\Theta }$-Greedy has a worst-case complexity of $O(n^3\log n)$, this bound is highly pessimistic. It assumes that Steps 4 and 5 spend $O(n\log n)$ time for every leaf-pair due to $A^{\ast }$ calls. In practice, this scenario rarely occurs. First, $A^{\ast }$ is seldom invoked because Greedy-Path successfully finds $t$-paths in most cases. When Greedy-Path is used, its directional exploration visits only a small fraction of vertices before terminating, making each check extremely fast. Second, when a long $t$-path is discovered between two distant leaves ${\sigma }_i,{\sigma }_j$, it typically suffices for almost all point pairs $p\in {\sigma }_i,q\in {\sigma }_j$, greatly reducing the number of subsequent calls. Combined with bridge reuse and shortcut caching, these effects make Steps 4 and 5 far cheaper than the worst-case analysis suggests. As a result, $\mathrm{\Theta }$-Greedy exhibits near-quadratic scaling in practice, as confirmed by our experiments on diverse synthetic and real-world datasets in Section 3.

The extra space needed by Prim’s algorithm and the Delaunay triangulation construction in Step 1 is $O(n)$. Constructing and storing $G_{\mathrm{\Theta }}$ takes $O(n)$ space. Greedy-Path and $A^{\ast }$ takes $O(n)$ extra space. The data structure shortcuts uses $O(n)$ space since, in the worst case, it can contain one $t$-path per edge in $G_{\mathrm{\Theta }}$. The quad tree $T$ in Step 4 uses $O(dn)$ space, where $d$ is its height. So, the extra space required by $\mathrm{\Theta }$-Greedy is $O(dn+|E^{\prime }|)=O(dn)$, since $|E^{\prime }|\le n$. Thus, $\mathrm{\Theta }$-Greedy behaves like a linear-space algorithm in practice, making it possible to generate spanners on point sets where $n$ is as large as ${10}^6$.

The algorithms were implemented in C++23 using GCC 13 and the CGAL 6.1 library [33]. The boost library was used for common algorithms and data structures. Refer to Table 2. All experiments were conducted on a desktop running Ubuntu Linux 24.04 LTS, equipped with an Intel Core i9-12900K processor and 32 GB of RAM. From CGAL, we employed the CGAL::Exact_predicates_inexact_constructions kernel. The entire codebase was compiled with the O3 optimization flag to maximize performance.

We used five point set distributions to generate random point sets. These distributions were adopted from previous experimental studies [6, 9, 23, 29, 32]. They are named uni-square, normal-clustered, grid-random, annulus, and spokes. Refer to Figure 4 for an illustration.

The uni-square distribution generates points uniformly within a square region using CGAL::Random_points_in_square_2. It is the most common distribution used in geometry experiments. The normal-clustered distribution places points in randomly positioned clusters, where each cluster follows a normal distribution with a fixed mean and standard deviation. Since the clusters are separated by long distances, shortest-path calls tend to take a long time. Hence, we chose it for our experiments. The grid-random distribution scatters points across a non-contiguous grid within a scaled square, with integer coordinates chosen uniformly at random. This distribution is important because of the collinearity present throughout its point sets. In Figure 4, although it resembles uni-square, the coordinates of the points are restricted to integers. The annulus distribution positions points inside a ring-shaped region defined by inner and outer radii, using real-valued uniform sampling. This distribution is important because of the large hole present inside the point sets. The spokes distribution organizes points along five radial spokes emanating from a central point. The vast separation between the collinear spokes is useful for testing spanner algorithms. For each of the above distributions, we considered eight values of $n$, selected from the set $\{1K,2K,\mathrm{\dots },128K\}$. For every value of $n$, we sampled five point sets.

Real-world point sets are essential because they reflect the actual spatial distributions and irregularities encountered in practical applications. Synthetic datasets, while useful for controlled benchmarking, often assume idealized conditions, such as uniform distributions, perfect clustering, or simplified geometries, that rarely occur in reality. Real-world data introduces challenges, such as uneven point density and non-uniform patterns, which may significantly influence spanner construction time and structural properties. Testing on real-world datasets ensures that algorithms are robust, scalable, and effective under realistic conditions. In our experiments, we used six real-world datasets, as described next.

The burma dataset consists of 33,708 points representing cities across Burma. The birch3 dataset contains 99,999 points arranged in random clusters scattered throughout the plane. The monalisa dataset is a 100,000-city TSP instance depicting a continuous-line drawing of the Mona Lisa. The KDDCU2D dataset includes 104,297 points corresponding to the first two dimensions of a protein dataset. The usa dataset represents a large-scale TSP instance with 115,475 cities covering nearly all towns, villages, and cities in the United States. Finally, the europe dataset comprises 168,435 points encoding differential coordinates of the European map. Refer to Table 3 for a summary.

Next, we compare $\mathrm{\Theta }$-Greedy with Bucketing using runtime, degree $\mathrm{\Delta }$, average degree (${\mathrm{\Delta }}_{\text{avg}}$), and lightness as metrics.

1. 1.

   Runtime. When constructing spanners on large point sets, runtime becomes a critical concern. Guaranteeing a $t$-path between every pair of points remains a significant challenge. For synthetic point sets, the maximum speedup was observed when $t=1.05$ (the smallest value used in our experiments) and $n=128K$. Refer to Figures 5, 6, 7, 8 and 9. For every value of $n$, the average runtime of five runs is reported. The corresponding speedups were $62.57$, $43.18$, $49.16$, $44.08$, and $40.78$ for uni-square, normal-clustered, grid-random, annulus, and spokes respectively. For real-world point sets (Table 4), the highest speedup of $147.59$ occurred for the europe dataset when $t=1.1$. As discussed next, $\mathrm{\Theta }$-Greedy achieved these speedups while maintaining low values of $a$ and $b$, ensuring high-quality $(a,b)$-doppelgängers. We also observed that Bucketing could match the speed of $\mathrm{\Theta }$-Greedy when $t=2$; however, in that case, $\mathrm{\Theta }$-Greedy can be easily accelerated further by using additional threads.

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   

   For point sets of size ${10}^6$, $\mathrm{\Theta }$-Greedy completed within a few hours (Table 6) using just one thread. Shariful et al. [32] reported that Bucketing requires about five days for the uni-square distribution, whereas $\mathrm{\Theta }$-Greedy finished in roughly two hours, corroborating its remarkable efficiency. For other distributions, $\mathrm{\Theta }$-Greedy consistently performed well, completing within a few hours. The slowest case was the normal-clustered point set, which took about four hours due to the presence of long $t$-paths in the final spanner, causing Greedy-Path and $A^{\ast }$ to run slower.

   

2. 2.

   Degree and average degree. Degree matters for load balancing and hardware constraints. For instance, in computer networks, a node with too many connections consumes more energy and bandwidth. Consequently, a low degree is desired. The average degree metric reflects the overall sparsity and efficiency of a network. A low average degree means fewer edges per vertex, reducing cost and complexity while maintaining connectivity.

   	uni-square	normal-clustered	grid-random	annulus	spokes	real-world
   $\max \left(a\right)$	0.0000	0.0000	0.0020	0.0010	0.0005	0.0000
   $\max \left(b\right)$	0.0000	0.0111	0.0056	0.0875	0.0030	0.0600

   According to the definition of $(a,b)$-doppelgängers, introduced in Section 1, lower values for $a$ and $b$ are desired. We found that for both synthetic and real-world point sets, the maximum value of $a$ did not exceed $0.002$, when all four values of $t$ were considered; refer to Table 5. This shows that $\mathrm{\Theta }$-Greedy is capable of producing greedy-like sparse spanners. To our knowledge, no other practical algorithm matches this performance.

   Regarding the actual difference in degrees, we observe that it is always $0$ for the real-world point sets (Table 4) and at most $4$ for the synthetic point sets. The maximum value of 4 occurs for the annulus instances, whereas for uni-square the difference remains 0.

3. 3.

   Lightness. It is crucial because it controls the total cost of connectivity. In real-world networks, such as transportation systems, wireless sensor deployments, or fiber-optic layouts, lower lightness means the network uses short edges while still guaranteeing good connectivity. This translates to lower construction costs, reduced energy consumption, and easier maintenance, making spanners both efficient and practical. As with the average degree, we found that the lightness of $\mathrm{\Theta }$-Greedy spanners was very close to that of Bucketing spanners. Refer to Table 5. For the synthetic point sets, the maximum value of $b$ was 0.0875, achieved for the annulus distribution. For the real-world point sets, it was $0.06$, achieved for the burma dataset, when $t=1.05$; see Table 4.

We now describe how $\mathrm{\Theta }$-Greedy is parallelized using OpenMP. The construction of the $\mathrm{\Theta }$-Graph is naturally parallelizable, since the edges generated for each point are independent. In Step 2, we process edges from $E_{\mathrm{\Theta }}$ in batches of size $T$, where $T$ is the number of threads. For each batch, we run $T$ instances of Greedy-Path in parallel. Let $T^{\prime }\le T$ denote the number of edges in the batch whose endpoints are not connected by a $t$-path, as determined by Greedy-Path. For these $T^{\prime }$ edges, $A^{\ast }$ is then executed sequentially to find $t$-paths and insert edges in $H$ whenever required. Since Greedy-Path successfully finds $t$-paths in most cases where such paths exist in $H$, calls to $A^{\ast }$ are comparatively infrequent. Detection of violating point pairs (i.e., pairs lacking $t$-paths) in the leaf nodes is independent in Step 3 and therefore parallelizable. In Steps 4 and 5, all leaf pairs $(\sigma ,{\sigma }_i)$, where $\sigma$ is fixed, are also processed in parallel.

The above approach yielded speedups proportional to $T$, making $\mathrm{\Theta }$-Greedy scalable for large point sets. Refer to Figures 10, 11, 12, 13, 14 and Tables 4 and 6. We observed consistent speedups across all values of $t$ used in our experiments.

Since Fast-Sparse-Spanner [32] was the only previously known practical algorithm for constructing spanners on large point sets, it is natural to compare our algorithm against it. Since one run of Bucketing on a million points takes several days (roughly 5 days for uni-square), it is impractical for comparison purposes. However, the trends show that $\mathrm{\Theta }$-Greedy spanners are still competitive with Bucketing spanners even for massive point sets. For instance, for the uni-square point set, we found the average degree to be $9.1$, which is roughly the same as that of the $100K$-element point set used in Section 1 (the reported value for Bucketing is $9.08$).

See Table 6, where we set $n={10}^6$ and $t=1.1$. The spanners produced by $\mathrm{\Theta }$-Greedy have significantly lower degrees than those generated by Fast-Sparse-Spanner, indicating that the resulting spanners differ substantially. The biggest differences were achieved for the uni-square and grid-random point sets. Interestingly, for the $128K$-element uni-square point sets, the maximum degree was at most 19 for $t=1.1$; the same value was observed even when $n={10}^6$. This demonstrates that our algorithm preserves greedy-like degree behavior even for massive point sets.

Although the differences in average degree are modest, the number of edges inserted by Fast-Sparse-Spanner is noticeably higher. For example, on the uni-square point set, Fast-Sparse-Spanner added roughly 455,000 more edges than $\mathrm{\Theta }$-Greedy. Moreover, the Fast-Sparse-Spanner spanners were substantially heavier than the $\mathrm{\Theta }$-Greedy spanners. This is primarily due to the long WSPD-spanner edges that Fast-Sparse-Spanner employs as a backbone. Taken together, these observations clearly demonstrate the superiority of $\mathrm{\Theta }$-Greedy over Fast-Sparse-Spanner.

Finally, the lightness of the $\mathrm{\Theta }$-Greedy spanners were significantly lower. See Table 6. The largest disparity occurred for the normal-clustered point set, where the lightness of the Fast-Sparse-Spanner graph was approximately $320$ times greater than that of the $\mathrm{\Theta }$-Greedy spanner.

We observe that Fast-Sparse-Spanner is faster than ours in practice. In particular, for uni-square, normal-clustered, grid-random, annulus, and spokes, the time taken by the algorithm was roughly $55$, $18$, $57$, $53$, and $19.07$ minutes, respectively, on a system comparable to ours using one thread. Fast-Sparse-Spanner, ran fastest on the normal-clustered point set due to the long WSPD-edges connecting distant clusters, owing to which $t$-path verifications terminated much faster compared to ours. In our case, the opposite happened, and we observed that $\mathrm{\Theta }$-Greedy was slowest on the same point set and took almost $4$ hours to finish due to the presence of much longer $t$-paths between distant clusters. With the increase in the number of threads ($T$), $\mathrm{\Theta }$-Greedy could accelerate in all five cases.