Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average-degreesResearch was supported by the NSF Award CCF-1947887.

FNU Shariful

School of Computing

University of North Florida, USA

Justin Weathers

School of Computing

University of North Florida, USA

Anirban Ghosh

School of Computing

University of North Florida, USA

Giri Narasimhan

Knight Foundation School of Computing and Information Sciences

Florida International University, USA

envelope<EMAIL_ADDRESS>
We design and engineer Fast-Sparse-Spanner, a simple and practical (fast and memory-efficient) algorithm  for constructing
sparse low stretch-factor geometric graphs on large pointsets in the plane. To our knowledge, this is the
first practical algorithm to construct fast low stretch-factor graphs on large pointsets with average-degrees (hence, the number of edges) competitive with that of
greedy-spanners, the  sparsest known class of Euclidean geometric spanners.

To evaluate our implementation in terms of computation
speed, memory usage,
and quality of output, we performed extensive experiments with
synthetic and real-world pointsets, and by comparing it to our
closest competitor Bucketing, the fastest known greedy-spanner algorithm for pointsets in the plane,
devised by Alewijnse et al. (Algorithmica, 2017).
We always found that Fast-Sparse-Spanner generated near-greedy $t$-spanners while being fast and memory-efficient.
Our experiment with constructing a $1.1$-spanner on a large
synthetic pointset with $128K$ points uniformly distributed within a
square shows more than a $41$-fold speedup with roughly a third
of the memory usage of that of Bucketing, but with only a 3$\%$
increase in the average-degree of the resulting graph. When ran on a pointset with a million points drawn from the same distribution, we observed a $130$-fold speedup, with roughly a fourth
of the memory usage of that of Bucketing, and just a $6\%$ increase in the average-degree.
In terms of diameter, the graphs generated by Fast-Sparse-Spanner beat greedy-spanners in most cases (have substantially lower diameter) while maintaining near-greedy average-degree. Further, our algorithm can be easily parallelized to take advantage of parallel  environments.

As a byproduct of our research, we design and engineer Fast-Stretch-Factor, a practical parallelizable algorithm that can
measure the stretch-factor of any graph generated by Fast-Sparse-Spanner.
Our experiments show
that it is much faster than the naive Dijkstra-based stretch-factor measurement algorithm.

We share the implementations via  for broader uses and future research.

GitHub repository. <https://github.com/ghoshanirban/FSS>

§ INTRODUCTION

Let $G$ be the complete Euclidean graph on a given set $P$ of $n$ points embedded in the plane. A
geometric $t$-spanner, or simply a $t$-spanner, on $P$ is a geometric graph $H := (P, E)$, a subgraph of $G$ such that for every pair of
points $p,q \in P$, the Euclidean length of a shortest path  between them in $H$
is at most $t$ times their Euclidean distance $|pq|$, for some $t \geq 1$. The parameter $t$ is referred to as the stretch-factor of $H$.
Thus, the subgraph $H$ approximately preserves pairwise shortest path distances for all point pairs in $P$.
The complete graph $G$ itself is a $1$-spanner
with $\Theta(n^2)$ edges. Clearly, for large values of $n$, complete graphs are unsuitable for practical purposes because of their sheer size. So, the main focus in the research of geometric spanners is to construct subgraphs having $o(n^2)$ edges and guarantee various structural properties. Refer to [50, 16] for an introduction to geometric spanners and [36, 24, 48, 7, 53, 52] for their uses. In this work, our objective is to engineer a practical algorithm that can construct low stretch-factor geometric spanners with low average-degrees[The average-degree of a graph $H:=(V,E)$ is defined as $2|E|/|V|$.].

Despite intensive theoretical studies on geometric spanners, how to construct sparse geometric spanners fast in practice on large pointsets with low average-degrees and low stretch-factors (less than $2$) remains unknown. Such spanners are used in real-world applications, whereas spanners with large stretch-factors are mainly of theoretical interest in computational geometry. In theoretical studies of spanners, bounds on the number of edges are typically expressed using asymptotic notations. As a result, owing to large hiding constants, many well-known algorithms are found to produce poor-quality spanners in practice, although novel asymptotic bounds have been obtained to prove them efficient. Farshi and Gudmundsson [31] were the first to perform a meticulous experimental study on geometric spanners. They found that the popular spanner algorithms suffer from at least one of the following limitations: (i) slow on large pointsets, (ii) memory-intensive, and (iii) places a high number of edges. Their study revealed a serious gap between the theory and practice of geometric spanners.

Xia showed that $L_2$-Delaunay triangulations are $1.998$-spanners [60] with at most $3n$ edges. Practical algorithms for constructing such triangulations exist; see [58].
There is a separate family of fast spanner construction algorithms that can create sparse bounded-degree plane spanners by using Delaunay triangulation (not necessarily using the $L_2$-norm) as the starting point; see [9, 8, 15, 28, 27, 43]. Unfortunately, in those algorithms, $t$ cannot be set arbitrarily.

Experiments and theoretical
studies [46, 47, 54, 56, 55, 31, 30, 29, 12, 4, 33]
have shown that greedy-spanners (a class of spanners whose
construction uses a greedy strategy), originally proposed by
Althöfer et al. [6] and Chandra et
al. [21],  are unbeatable, especially when one desires to minimize
the number of edges  (alternatively, average-degree), for any desired stretch-factor. See
Algorithm <ref> for a description of the
original greedy algorithm, popularly known as Path-Greedy
and Fig. <ref> for greedy-spanner samples for various values of $t$. Path-Greedy  is a generalization of the folkore Kruskal’s minimum spanning tree algorithm and produces sparse spanners. A demonstration applet for the algorithm can be found in [32].

Sort and store the $\binom{n}{2}$ pairs of distinct points in non-decreasing order of their distances  in  a list $L$
Let $H$ be an empty graph on $P$
each edge $\{p_i,p_j\} \in L$
the length of a shortest path in $H$ between $p_i,p_j$ is greater than $t \cdot |p_ip_j|$
Place the edge $\{p_i,p_j\}$ in $H$

Path-Greedy$(P,t> 1)$

Four greedy-spanners on a set of $150$ points in the plane are shown, having stretch-factors of $1.05, 1.1, 1.25, 2$, respectively. In this case, the complete graph $G$ has $\binom{150}{2}  = 11,475$ edges.

The first attempt to construct near-greedy sparse spanners fast
was made by Das and Narasimhan back in $1997$ [25]. Their algorithm Approximate-Greedy runs in $O(n\log^2 n)$-time and is thus substantially faster than  Path-Greedy, that runs in $O(n^3\log n)$ time. Unfortunately, it was observed in [31] that, in practice, the average-degrees of the graphs produced by Approximate-Greedy are far from that of the actual greedy-spanners. A slightly faster $O(n\log n)$-time algorithm was designed in [39] by Gudmundsson, Levcopoulos, and Narasimhan to approximate greedy-spanners. Since the algorithm is quite involved, we did not implement it for comparison purposes. We observe that the algorithm is designed along the lines of Approximate-Greedy, and therefore, we believe that it will  unlikely generate  spanners sparser than the ones generated by   Approximate-Greedy.

Farshi and Gudmundsson [31] presented a simple modification of the original   Path-Greedy algorithm to
make it faster in practice by reducing the number of single-source
shortest path computations using an additional matrix; see
Algorithm <ref>. It is sometimes referred to as
FG-Greedy. 	But in theory, both the Path-Greedy and FG-Greedy algorithms run in $O(n^3\log n)$ time.  Further, due to the use of $\binom{n}{2}$ edges in the
Path-Greedy and FG-Greedy algorithms (see Step 1),
$\Theta(n^2)$ extra space is needed for their execution. Consequently,
they are unusable for large pointsets.

Sort and store the $\binom{n}{2}$ pairs of distinct points in non-decreasing order of their distances  in  a list $L$
Let $H$ be an empty graph on $P$
$(p_i,p_j) \in P \times P$
$\texttt{weight}(p_i,p_j) = \infty$;

each edge $\{p_i,p_j\} \in L$
$(p_i,p_j) > t \cdot |p_ip_j|$
Compute single-source shortest path with source $p_i$ in $H$

$q \in P$
Update $(p_i,q)$ and $(q,p_i)$ to the weight of the shortest path found between $p_i$ and $q$ in the previous step

$(p_i,p_j) > t \cdot |p_ip_j|$
Place the edge $\{p_i,p_j\}$ in $H$

FG-Greedy$(P,t> 1)$

In the same paper [31], Farshi and Gudmundsson experimentally
found that for low values of $t$
(for example $t \le 1.25$),
greedy-spanners always tend to be considerably sparser than other
popular kinds of spanners such as the
$\Theta$-Graphs [14, 23, 44],
WSPD-spanners [18],
Sink-spanners [10], Skip-list-spanners [10], and Approximate-Greedy-spanners [25].

Bose et al. [13] devised a faster algorithm for
constructing exact greedy-spanners in $O(n^2\log n)$ time, but
unfortunately, like Path-Greedy and FG-Greedy, their
algorithm uses $\Theta(n^2)$ space as well. They also showed that
runs in $\Theta(n^3\log n)$ time since previously it was suspected
that it runs in $o(n^3\log n)$ time.

Alewijnse et al. [4] presented an
$O(n^2\log^2 n)$-time algorithm for constructing greedy-spanners.
Although the algorithm is asymptotically slower than the algorithm
designed by Bose et al. [13], it uses linear
space. It was a significant breakthrough in this line of research. A
faster algorithm, named Bucketing, was presented by Alewijnse et al.
in [5] that runs in $O(n\log^2 n \log^2
\log n)$ expected time. They observe that greedy-spanners are made up
of `short' and `long' edges.
Short edges are identified using a bucketing scheme, while long edges
are computed using a WSPD (well-separated pair decomposition).
They also experimentally showed that their algorithm is considerably
faster than the one proposed in [4] and uses
a reasonable amount of memory, making it the best greedy-spanner
algorithm so far. For this reason, we have excluded the algorithm proposed in [4] in our experiments.
Although being capable of producing arguably the best quality class of geometric spanners, we found that Bucketing
becomes very compute-intensive when $t$ approaches $1$ (such $t$-values are more useful in practice),
making it slow on large pointsets.
For instance, it takes around $100$ minutes on a fast modern-day
computer equipped with an  processor, to compute a $1.1$-spanner on a $128K$-element pointset uniformly
distributed inside a
square. For a million points drawn from the same distribution, it takes around five days on the same machine to run to completion, making it impractical for large pointsets.

Recently, Abu-Affash et al. [2] devised a new
algorithm named $\delta$-Greedy that can produce greedy-like spanners
in $O(n^2\log n)$ time. When $\delta$, a parameter used in the algorithm, is set to $t$, it
outputs spanners identical to that of Path-Greedy.
Although experimentally shown to be
speedy in practice,
it remains impractical
for large values of $n$
since it uses $\Theta(n^2)$ extra space. In fact, Step 1 in their algorithm is precisely the same as the one in Path-Greedy and FG-Greedy, contributing to quadratic space complexity. We found that $\delta$-Greedy, Path-Greedy,  FG-Greedy, and the $O(n^2\log n)$-time algorithm presented by Bose et al. [13] are impractical and run out of memory (on a machine equipped with $32$ GB of main memory) when $n$ is large. For instance, when $n=100K$, to store the complete graph edges in a list, we need $2\cdot \binom{100K}{2} \cdot 4 \text{ bytes} = 40~\text{GB}$ of main memory, assuming every edge is represented using a pair of $4$-byte integers. For this reason, we have excluded the above four algorithms from our experiments.

§.§ Our contributions

* Motivated by the
lack of a fast near-greedy-spanner construction algorithm for handling large pointsets,
we have designed and engineered a fast and memory-efficient  construction
algorithm that we have named Fast-Sparse-Spanner (see
Section <ref>). The algorithm is simple and intuitive
and has been designed by observing how sparse spanners look in
practice as opposed to the traditional approaches where
obtaining theoretical bounds is the main focus. Of course,
existing theory on spanners have been leveraged to design the
While, theoretically, the algorithm is not guaranteed to
produce $t$-spanners, we conjecture in Section <ref>
that for uniform distributions, its output is a $t$-spanner
with high probability.
In our experiments with more than $25K$ trials using synthetic and real-world pointsets of varied sizes, we
found that it always produced fast, near-greedy sparse
$t$-spanners, even for $t$ as low as $1.05$. This inspired us to name our algorithm Fast-Sparse-Spanner. In real-world applications, sometimes fast and memory-efficient constructions of sparse geometric graphs is a necessity even if their actual stretch-factors are close the desired stretch-factors. Thus, our algorithm is still useful even if it misses stretch-factors in some cases (in our experiments, we never found so). We believe that if it ever misses the target stretch-factor, the actual stretch-factor of the generated geometric graph will not be far away from the target. Fast-Sparse-Spanner can  easily  leverage modern-day parallel environments (multi-core CPUs, for instance) for scalability.

Using a preliminary experiment by comparing it with $\Theta$-Graphs, WSPD-spanners, Sink-spanners, Skip-list-spanners, Approximate-Greedy-spanners, and the spanners produced by Bucketing, we show that Bucketing is our closest competitor when average-degree is the main concern. Thereafter, we  compare
Fast-Sparse-Spanner with Bucketing and show real-world efficacy of our algorithm by running it on large synthetic and real-world pointsets.
Fast-Sparse-Spanner can construct near-greedy sized geometric graphs and is considerably
faster  than Bucketing, especially for low stretch-factors. For instance, on our machines, it could construct a $1.1$-spanner on a $128K$-element uniformly distributed pointset inside a square within $2.5$ minutes and used $65\%$ less extra memory compared to Bucketing while placing only $3\%$ extra edges. For a million points drawn from the same distribution, it finished its execution in around $55$ minutes using around $1.3$ GB of main memory, making it remarkably faster than Bucketing which took around 5 days and used $5.8$ GB of main memory. In this case, we observed just a $6\%$ increase in the number of edges compared to the graph produced Bucketing.

In most cases, we found that the spanners generated by our algorithm have substantially lower diameters than the greedy-spanners while maintaining near-greedy average-degrees. For instance,  $1.1$-spanners generated by Fast-Sparse-Spanner on $128K$-element uniformly distributed pointsets have diameters around $25$, whereas greedy-spanners have around $200$.

We compare the spanners generated by our algorithm to the ones produced by Bucketing in terms of
average-degree and diameter[The diameter of a graph $G$ is the length (number of edges) of the longest shortest path among all vertex pairs in $G$.] (see Section <ref>).   For broader uses and future research in this direction, we share our engineered  code via .

* To our knowledge, there are no practical algorithms for measuring the
stretch-factors of large spanner networks. However, an attempt has been made by Narasimhan and Smid to approximate stretch-factors of geometric spanners in [49]. Chen et al. [22] devised algorithms for approximating average stretch-factors of geometric spanners. Stretch-factor measurement algorithms for special types of geometric graphs such as paths, cycles,  trees, and plane graphs, can be found in [3, 59, 9]. Klein et al. [45] devised algorithms for reporting all pairs of vertices
whose stretch factor is at least some given value $t$, when the input graph is a geometric path, tree, or cycle.
Distance oracles can be used to estimate stretch-factors of geometric graphs. In this regard, Gudmundsson et al. [40] presented distance oracles for geometric spanners. For a discussion on shortest path queries for static weighted graphs including distance oracles, refer to the survey [57] by Sommer.
Surprisingly, the only known easy-to-engineer stretch-factor measurement  algorithm that works for any type of Euclidean graph, runs in $O(n^2\log n + n|E|)$ time by running the folklore Dijkstra's algorithm from every node [49], making it very slow for large spanners. When the input graph is sparse, this approach runs in $O(n^2\log n)$ time. Use of the Floyd-Warshall algorithm is even more impractical since it uses $\Theta(n^2)$ extra space. Sub-cubic all-pairs shortest path (APSP) algorithms exist, but those are involved and are seemingly challenging to engineer; see the paper [20] by Chan and the references therein. A $O(n^{2.922})$-time stretch-factor measurement algorithm follows directly from the $O(n^{2.922})$-time APSP algorithm presented by Chan in the same paper for Euclidean graphs.

In this work, by exploiting the construction of the spanners generated by Fast-Sparse-Spanner, we have designed a new practical algorithm named Fast-Stretch-Factor that can compute stretch-factor of any spanner generated by Fast-Sparse-Spanner (see Section <ref>). Further, it is easily parallelizable. Our experiments found that it is substantially faster than the naive Dijkstra-based algorithm (see Section <ref>). For instance, for a spanner constructed on a $1M$-element pointset uniformly distributed  inside a square and $t=1.1$, Fast-Stretch-Factor ran to completion in around $47$ minutes, whereas the Dijkstra-based algorithm took around $22$ hours when $4$ threads were used in both the cases.

§.§ Preliminaries and notations

Let $P$ and $Q$ be two finite pointsets and $s$ be a positive real number. We say that $P$ and $Q$ are well-separated with respect to $s$, if there exist two congruent disjoint disks $D_P$ and $D_Q$, such that $D_P$ contains the  bounding-box of $P$, $D_Q$ contains the  bounding-box of $Q$, and the distance between $D_P$ and $D_Q$ is at least $s$ times the common radius of $D_P$ and $D_Q$. The quantity $s$ is referred to as the separation ratio of the decomposition.

Using the above idea of well-separability, one can define a well-separated decomposition (WSPD) [19]  of a pointset in the following way. Let $P$ be a set of $n$ points and $s$ be a positive real number. A WSPD for $P$ with respect to $s$ is a collection of pairs of non-empty subsets of $P$,
for some integer $m$ (referred to as the size of the WSPD) such that

for each $i$ with $1 \leq i \leq m$, $A_i$ and $B_i$ are well-separated with respect to $s$, and
for any two distinct points $p,q \in P$, there is exactly one index $i$ with $1 \leq  i \leq m$, such that  $p \in A_i, q \in B_i$, or $p \in B_i, q \in A_i$.

Given a pointset $P$ and $t>1$, a WSPD $t$-spanner [18, 50, 38] on $P$ is constructed in the following way. Start with an empty graph $H$ on $P$. Let $s = 4(t+1)/(t-1)$. Construct a WSPD of $P$ with separation ratio $s$.
For every pair $\{A_i,B_i\}$ of the decomposition, include the edge $\{a_i,b_i\}$ in $H$, where $a_i$ is an arbitrary point in $A_i$ and $b_i$ is an arbitrary point in $B_i$.

Given a pointset $P$ and a positive integer $k$, a region quad-tree [34] (or simply, a quad-tree) on $P$ is a $4$-ary tree in which every node has either four children or none and is constructed by partitioning the bounding-box $B$ of $P$ into four equal-sized quadrants and creating four corresponding children attached to the root of the tree.
For each child with more than $k$ points from $P$ inside its quadrant, recursively create a quad-tree rooted at the child by dividing its quadrant into four equal-sized sub-quadrants. With every leaf,  store the points in $P$ located inside it.

A leaf of a quad-tree is said to be empty if it does not contain any point in $P$.

Let $H$ be an Euclidean graph on $P$ and  $u,v \in P$. A path $\rho(u,v)$ between $u,v$ in $H$ is a $t$-path for $u,v$ if the Euclidean length of the path $\rho(u,v)$ is at most $t$ times $|uv|$. It can be observed that $H$ is a $t$-spanner if and only if at least one $t$-path exists in $H$ for every pair of points in $P$.

§ A  NEW PRACTICAL HYBRID  ALGORITHM

It is well known
that greedy algorithms are found to be slow in
practice on large pointsets, especially for low stretch-factors  but are
best for generating extremely sparse spanners. 	This motivated us to  construct local greedy-spanners on small disjoint chunks of $P$ to reduce the overall runtime.
Then, we carefully and efficiently “stitch” (merge)
the local greedy-spanners
into one final graph using long and short edges.
In practice, we found that the number of edges needed to merge them is
not too many. This gives us a practical geometric graph construction algorithm
that is competitive with the greedy-spanner algorithms with respect to
the number of edges placed, while being fast and memory efficient. Our algorithm,
Fast-Sparse-Spanner  uses FG-Greedy, WSPD-spanner,
and a layering strategy to incrementally compute $H$,
a subgraph of $G$ (the complete Euclidean graph on $P$). Refer to Algorithm <ref>.

Let $H$ be an empty graph on $P$

Create a quad-tree $T$ on $P$ such that the size of every leaf is at most $k$

$S = \emptyset$;

each non-empty leaf $\sigma \in T$
$P_\sigma = P \cap \sigma$
Construct a greedy-spanner $H_\sigma$ on $P_\sigma$ using FG-Greedy$(P_\sigma,t)$ (Algorithm <ref>)
$H = H \cup H_\sigma$
$S = S \cup \ell_{\sigma}$, where $\ell_\sigma$ is the leader point of $\sigma$

Create a WSPD $t'$-spanner $W$ on $S$ and add
the edges of $W$ in $H$

Let $G_T$ be the dual graph on the leaves of $T$, where the edge $\{\sigma_i,\sigma_j\} \in G_T$ if and only if the leaves $\sigma_i,\sigma_j$ are neighbors

every non-empty leaf $\sigma \in T$

every non-empty neighbor $\sigma'$ of $\sigma$ in $G_T$
$\sigma,\sigma'$ are both non-empty and have  not been merged yet
$\textsc{Greedy-Merge}(\sigma,\sigma',t,H)$ (Algorithm <ref>)

$i=2$ to $h$
each non-empty leaf $\sigma \in T$

each non-empty leaf $\sigma'$  that is $i$ hops away from $\sigma$ in $G_T$
$\sigma,\sigma'$ are both non-empty and have not been merged yet
$\textsc{Greedy-Merge-Light}(\sigma,\sigma',t,H)$ (Algorithm <ref>)

Fast-Sparse-Spanner$(P,t > 1,t'\geq t,k\in \mathbf{Z}^+,h \in \mathbf{Z}^+)$

In Section <ref>, we present precise values for the three parameters $t',k,h$ used in our experiments.
In what follows, we provide details on the steps.

* Step 1.  Create a region quad-tree $T$ on $P$ where the size of every leaf is at most $k$. Later, in our experiments, we fix a suitable value for $k$. The region quad-tree aids in partitioning $P$ into almost same-sized disjoint chunks.

* Step 2.  For every non-empty leaf $\sigma$ of $T$, we create a local greedy $t$-spanner $H_\sigma$ on $P_\sigma$ using FG-Greedy (Algorithm <ref>), where $P_\sigma = P \cap \sigma$. All the edges of the local greedy-spanners are placed in $H$.   Further, for every leaf $\sigma \in T$, we find its leader point $\ell_\sigma$, a point in $P_\sigma$ that is closest to the center of the bounding-box of $P_\sigma$. In the cases of ties, choose arbitrarily.

* Step 3.  Let $S := \cup_{\sigma \in T}
\ell_\sigma$. Create a WSPD-spanner $W$ on $S$
with stretch-factor $t'\geq t$ using the $O(n\log n)$ time
algorithm presented in [50]; an
efficient implementation can also be found in [51].  Include the edges
of $W$ in $H$.
This creates a strong network on the leaders of the
non-empty leaves. Consequently, the non-empty leaves of $T$
are now connected using the edges of $W$. See Fig. <ref> (left) for an illustration.

Left: A WSPD-spanner on the leaders of the non-empty leaves. Right: The dual graph $G_T$ on the leaves of the quad-tree.

Unlike greedy-spanners, WSPD-spanners tend to have long edges. In our case, this is beneficial since such long WSPD edges also help reduce the diameter of the final output spanner. For faraway point pairs, shortest paths use the long WSPD edges placed in this step. As a result, path-finding algorithms (described next) terminate fast in most cases.
Note that after this step, $H$ becomes a connected graph on $P$ since the intra-leaf point pairs are connected via the local greedy-spanners and the inter-leaf point pairs are connected via local greedy spanners and the WSPD-spanner edges.

* Step 4.  We create a dual graph $G_T$ on the  leaves of $T$ where the edge $\{\sigma_i,\sigma_j\} \in G_T$ if and only if the leaves $\sigma_i,\sigma_j$ are neighbors in $T$ (their bounding-boxes intersect). See Fig. <ref> (right). To find the neighboring leaves of a leaf $\sigma$,  we dilate the box corresponding to  $\sigma$ by a small quantity, and find the intersecting leaves by spawning a search at the root of $T$.
It is easy to check that $G_T$ is connected.
Using Greedy-Merge (Algorithm <ref>), we “stitch” (merge) the local spanners inside every pair of non-empty neighbors $\sigma_i,\sigma_j$ in $G_T$ and ensure $t$-paths between all point pairs in $P_i \times P_j$, where $P_i:=P\cap \sigma_i,P_j:=P\cap \sigma_j$. See Fig. <ref> for an illustration. However, in our algorithm, to minimize the number of edges placed during the mergings, we consider the whole spanner constructed so far when we look for $t$-paths. From now on, by merging two non-empty leaves in $G_T$, we mean merging the two local spanners inside them, as explained above.

Two separate greedy $1.25$-spanners are constructed on the red and blue points. Then, the two spanners are merged by placing the dashed edges and ensuring $1.25$-paths for all point pairs $u,v$ where $u$ is red and $v$ is blue. The closer the two spanners are, the more edges may be needed to merge them.

After completion of this step, the number of point pairs not having $t$-paths reduces drastically. Now we give a description of Greedy-Merge.
Let $L := P_i \times P_j$.
Check for the existence of the edge $e:=\{\ell_{\sigma_i}, \ell_{\sigma_j}\}$ in $H$. If $e$ exists, then it was placed in Step 3.
If $e \in H$, prune pairs from $L$ in the following way.  For every pair $(u,v) \in L$,  find the lengths of the following three paths: a shortest path from $u$ to $\ell_{\sigma_i}$ in $H$, the length of the edge  $e$, and a  shortest path from $\ell_{\sigma_j}$ to $v$ in $H$. Let the lengths of these three paths be $a,b,c$, respectively. If $(a+b+c) / |uv| \leq t$ (a $t$-path between $u,v$ already exists in $H$),  remove $(u,v)$ from $L$.  Note that the two paths $u$ to $\ell_{\sigma_i}$ and $\ell_{\sigma_j}$ to $v$ always exist because of the local greedy $t$-spanners already created inside every non-empty leaf.  In our experiments, we found that owing to careful edge placements  by FG-Greedy, the lengths of the shortest paths between any two points $u,v$ from the same leaf is very close to and at most $t \cdot |uv|$. So, instead of storing the path lengths obtained from the FG-Greedy executions or recomputing them, we use the quantities $t\cdot |u\ell_{\sigma_i}|$ and $t\cdot |\ell_{\sigma_j}v|$ as a substitute of their shortest path lengths. This adjustment saves us time and memory without any visible increase in the average-degree of $H$. Next, we sort $L$ (after possible pruning) based on the
Euclidean distance of the point pairs. Akin to
FG-Greedy, the sorting step helps to reduce the new
edges placed to merge two local greedy-spanners inside

Let $L = P_i \times P_j$, where $P_i, P_j$ are the pointsets inside the leaves $\sigma_i,\sigma_j$, respectively

the edge $\{\ell_{\sigma_i},\ell_{\sigma_j}\} \in H$

each $(u,v) \in L$

$\dfrac{t\cdot|u\ell_{\sigma_i}| + |\ell_{\sigma_i}\ell_{\sigma_j}| + t\cdot |\ell_{\sigma_j}v|}{ |uv|}\leq t$

$L = L \setminus \{(u,v)\}$

Sort $L$ according to the Euclidean distance of the point pairs
$\texttt{bridges} = \emptyset$;

each $\{u,v\} \in L$
$\nexists$ $x\curly y \in \texttt{bridges}$ such that $\dfrac{t\cdot |ux| + |x\curly y| + t \cdot |yv|  } {|uv| }\leq t$
the path $u \curly v$ returned by Greedy-Path$(H,u,v)$ is a $t$-path between $u,v$
$\texttt{bridges}  = \texttt{bridges} \cup \{u \curly v\}$

the shortest path $\pi(u,v)$ between $u,v$ returned by $A^*$ is a $t$-path

$\texttt{bridges}  = \texttt{bridges} \cup \{\pi(u,v)\}$

Place the edge $\{u,v\}$ in $H$
$\texttt{bridges}  = \texttt{bridges} \cup \{\{{u,v}\}\}$

A bridge is a path that connects two
vertices $u \in P_i,v\in P_j$. We maintain a set of  found so far.
For every pair $(u,v) \in L$, first we check if there is a bridge $x\curly y \in \texttt{bridges}$  such that the path from $u$ to $v$ via the bridge $x\curly y$ is a $t$-path for $u,v$. If there is none, we check if there is a $t$-path between them in $H$. The main objective behind caching all the bridges found so far is to reuse them for the future point pairs since we found that Greedy-Merge does not put many bridges while trying to ensure $t$-paths among all point pairs. Consequently, we are able reduce the number of expensive  $t$-path computations.

Mark $u$  and  all vertices in $P\setminus \{u\}$

$y\neq v$
Let $X$ be the set of neighbors of $y$ in $H$ currently marked
$X$ is emptyReport path cannot be found
Find the neighbor $x \in X$ that minimizes $|yx| + |xv|$
Append $x$ to
$x == v$break

For finding a $t$-path between a vertex pair $u,v$, we first find a path using Greedy-Path (Algorithm <ref>) and check if the path returned by it is a $t$-path between $u,v$ in $H$. It iteratively constructs a path (not necessarily a shortest one) starting at $u$ by including the next neighbor $x$ of the current vertex $y$ that minimizes the Euclidean distance between $y$ and $x$ plus the Euclidean distance between $x$ and $v$.   If the path returned is not a $t$-path for $u,v$, we run $A^*$,  a popular Dijkstra-based shortest path algorithm that runs fast on geometric networks [41], to find a shortest path $\pi(u,v)$ between $u,v$ in $H$. Then, we verify if $\pi(u,v)$  is a $t$-path between $u,v$.
We note that Greedy-Path does not use a priority-queue like $A^*$, and as a result, it tends to be faster and uses less memory. For instance, for a $512K$-element pointset uniformly distributed inside a square, using Greedy-Path made our algorithm $\approx 23.5\%$ faster. As explained in Section <ref>, Greedy-Path could find $t$-paths in most cases. As a result, the number of $A^*$ calls was much less than the number of Greedy-Path calls.

If a $t$-path is found, we put the $t$-path between $u,v$ in . Otherwise, we place the edge $\{u,v\}$ both in $H$ and .

In our experiments, we found that after this step, the number of point pairs that do not have $t$-paths between them in $H$ is very low and sometimes is even zero.

* Step 5.
For every non-empty leaf $\sigma \in T$, we merge $\sigma$  with the  leaves in $T$ that are at least $2$ and at most $h$ hops away from it in $G_T$ (constructed in Step 4).
Note that in Step 4, we already merged $\sigma$ with the leaves that are exactly one hop away from it in $G_T$. However, we do this incrementally. First, we merge every leaf with its $2$-hop neighbors, then with its $3$-hop neighbors, and so on. In this step, we use a lighter version of the merge algorithm used in the previous step. The sorting step in Greedy-Merge takes a substantial amount of time since it sorts $|P_i| \cdot |P_j|$ point pairs and for merging the pointsets inside distant leaves ($2$ hops or more away from each other in $G_T$), we replace the sorting step with the following faster alternative.  Sort the points in $P_i$($P_j$) based on their distances from the leader point of the points inside the other leaf $\sigma_j$($\sigma_i$). In this case, we execute sorting twice; once on $|P_i|$ pairs and another time on $|P_j|$ pairs. Then we use a pair of nested loops to work with the point pairs, as shown in Algorithm <ref>.
We call this slightly modified merging algorithm

Let $P_i, P_j$ be the two pointsets inside the leaves $\sigma_i,\sigma_j$, respectively

Sort $P_i$ based on their distances from the leader point   $\ell_{\sigma_j}$

Sort $P_j$ based on their distances from the leader point $\ell_{\sigma_i}$

$\texttt{bridges} = \emptyset$
the edge $\{\ell_{\sigma_i},\ell_{\sigma_j}\} \in H$
$\texttt{bridges} = \texttt{bridges} \cup \{\{\ell_{\sigma_i},\ell_{\sigma_j}\}\}$

each $u \in P_i$
each $v \in P_j$
$\nexists$ $x\curly y \in \texttt{bridges}$ such that $\dfrac{t\cdot |ux| + |x\curly y| + t \cdot |yv|  } {|uv| }\leq t$
the path $u \curly v$ returned by Greedy-Path$(H,u,v)$ is a $t$-path between $u,v$
$\texttt{bridges}  = \texttt{bridges} \cup \{u \curly v\}$

the shortest path $\pi(u,v)$ between $u,v$ returned by $A^*$ is a $t$-path

$\texttt{bridges}  = \texttt{bridges} \cup \{\pi(u,v)\}$

Place the edge $\{u,v\}$ in $H$
$\texttt{bridges}  = \texttt{bridges} \cup \{\{{u,v}\}\}$

Since the merging of leaf pairs that are relatively
far from each other
rarely need placement of new edges after Step 4, this modified step has almost the same effect as that of the sorting used in the previous step. Due to the higher number of mergings  required in this step (compared to Step 4), we use Greedy-Merge-Light to speed up our algorithm in practice. For instance, for a $1M$-element  pointset uniformly distributed inside a square, using Greedy-Merge-Light in Step 5 instead of Greedy-Merge helped the algorithm to speed up by a factor of $2$ but with a negligible increment of $0.1$ in the average-degree of the final spanner.

In the following, we show that $H$ is sparse. We first present Lemma <ref>, which is  subsequently used to prove Theorem <ref>.

Let $S$ be a  set of leaves of the quad-tree $T$ (constructed in Step 1). Then, the subgraph $G_T(S)$ of $G_T$, induced by $S$ has $O(|S|)$ edges.

Two leaves in $S$ form a diagonal pair if they intersect only at a point otherwise they form a non-diagonal pair. An edge in $G_T(S)$ connecting the leaves of a diagonal pair is a diagonal edge; otherwise, it is a non-diagonal edge. Let the number of diagonal edges in $G_T(S)$ be $a$ and the non-diagonal edges be $b$.

Since every leaf in $S$ can form a diagonal pair with at most four other leaves in $S$, $a = O(|S|)$. Now we estimate the number of non-diagonal edges in $G_T(S)$.
Construct a geometric graph $G$  using the leaves in $S$. For every leaf $\sigma \in S$, we consider its center to be a vertex in $G$. Place an edge (a  line-segment) between two vertices in $G$ if and only if the corresponding two leaves form a neighboring non-diagonal pair.  Every leaf $\sigma \in S$ forms a star centered at its center, with its adjacent non-diagonal leaves in $S$. We observe that these stars are plane (crossing-free). Refer to Fig. <ref>.
$G$ is a union of the stars centered at the  leaves in $S$.  So, $G$ is plane graph on $O(|S|)$ vertices. Consequently, $G$ has $O(|S|)$ edges. This implies, $b=O(|S|)$

Thus, we conclude that $G_T(S)$ has $a+b=O(|S|)+ O(|S|) = O(|S|)$ edges.

The non-empty leaves are shown in gray. The red, blue, green, and yellow leaves are the empty north, east, south, and west  neighbors of the non-empty leaf $\sigma$, respectively.

For fixed values of $h$ and $k$, $H$ is a  geometric graph on $P$ with $O(n)$ edges.

Since $k=O(1)$, the  size of every greedy-spanner constructed by FG-Greedy inside every leaf is $O(1)$. The quad-tree $T$ has $O(n)$ non-empty leaves. So, the total number of edges put by FG-Greedy in Step 2 is $O(n)$.
The WSPD-spanner $W$ constructed in step 3 on $O(n)$ leaders contains $O(n)$ edges [50]. Thus, the total number of edges put so far in $H$ is $O(n)$.

Next, we show that the algorithm places $O(n)$ edges in $H$ in steps 4 and 5. To show this, we estimate the number of mergings $m$, executed in the Steps 4 and 5. Since the size of every non-empty leaf of the quad-tree $T$ is no more than $k$, every merging places at most $O(k^2)=O(1)$ edges in $H$. It remains to show that $m=O(n)$.

As every merging requires at least one non-empty leaf (the other non-empty leaf is at most $h$ hops away in $G_T$),    $m$  equals $h$ times the total number of edges $q$ incident on the non-empty leaves of $T$ in $G_T$. Now we shall estimate $q$ and show that $q = O(n)$.

Let $A$ be the set of non-empty leaves in $T$.
Consider any leaf $\sigma \in A$. For every non-empty leaf $\sigma'$ (possibly same as $\sigma$), there can be at most two of its empty sibling leaves which are the east neighbors of $\sigma$. Refer to Fig. <ref>.
Since there are $O(n)$ non-empty leaves, the total number of empty east neighbors for all the non-empty leaves in $T$ is also $O(n)$. Similarly, the total number of north, south, and west empty neighbors is also $O(n)$ each.
Thus, there are a total of $O(n)$ empty neighbors of the non-empty leaves. We denote the set of such empty neighbors by $B$. Further, let $C$ be the set of diagonal neighbors of the non-empty leaves. Clearly, $|C|=O(n)$.
Now, let $G_T(A \cup B \cup C)$ be the subgraph of $G_T$, induced by the vertices in $A\cup B \cup C$. By Lemma <ref>, $G_T(A\cup B \cup C)$ has $O(|A \cup B \cup C|) = O(|A| + |B| + |C|)= O(n + n + n) = O(n)$ edges.

Since $h$ is a constant, $m = h \cdot q = O(1) \cdot O(n) = O(n)$. Hence, $H$ has $O(n)$ edges.

For fixed values of $h$ and $k$, the total number of mergings executed by Fast-Sparse-Spanner is $O(n)$.

Now, we focus on our algorithm's time and space complexities.

For fixed values of $h$ and $k$,
Fast-Sparse-Spanner runs in $O(n^2\log n + d^2n)$ time and uses $O((d+1)n)$ extra space, where $d$ is the depth of the quad-tree $T$ used in Step 1.

The construction of the quad-tree $T$ in Step 1 takes $O((d+1)n)$ time <cit.>. Since there are $O(n)$ non-empty leaves of $T$, our algorithm makes $O(n)$ FG-Greedy calls, each on a pointset of size at most $k=O(1)$. Thus, Step 2 takes $O(n)$ time. The construction of the WSPD-spanner $W$ in Step 3 takes $O(n\log n)$ time.

Now we estimate the time taken to construct $G_T$. Let $n_v$ denote the number of neighbors of a vertex $v$ in $G_T$. The time taken to find $n_v$ neighbors of $v$ by doing a 4-way search starting at the root of the quad-tree $T$ is $O(d)\cdot n_v$. Since $G_T$ has $O((d+1)n)$ leaves <cit.>, by Lemma <ref>$, G_T$ has $O((d+1)n)$ edges. So, the total time taken to compute $G_T$ is,
$$\sum_{v \in G_T} ( O(d) \cdot n_v ) = O(d) \sum_{v \in G_T} n_v = O(d)\cdot O((d+1)n) = O(d^2 n).$$

We use $O(n)$ breadth-first traversals to find the leaves that are at most $h$ hops away. Since $G_T$ has $O((d+1)n)$ edges and $h=O(1)$, total time taken for the $n$ traversals amounts to $O(h(d+1)n) = O((d+1)n)$.

Since $H$ is sparse (Theorem <ref>), each execution of Greedy-Path and $A^*$ takes $O(n)$ and $O(n\log n)$ time each, respectively.
The sorting calls in Greedy-Merge and Greedy-Merge-Light run in $O(1)$ time each since $k=O(1)$.
By Corollary <ref>, our algorithm executes $O(n)$ mergings. Every merging considers at most $k^2 = O(1)$ point pairs (some leaves in $T$ may contain less than $k$ points).
For every such point pair, $O(k^2 + O(n) + O(n\log n)) = O(k^2 + n\log n)$ time is spent to verify the existence of a $t$-path in $H$, since there are $O(k^2)$ bridges in the worst case. So, the total time spent in the Steps 4 and 5 is $O(n\cdot k^2 \cdot  (k^2 + n\log n)) = O(n^2\log n)$.

Summing up all the above runtimes gives us a runtime of $O(n^2\log n + d^2n)$ for the Fast-Sparse-Spanner.

Now we analyze its space complexity.
The quad-tree $T$  needs $O((d+1)n)$ storage space <cit.>. Step 2 uses $O(1)$ extra space since FG-Greedy is run on $k=O(1)$ points. The  construction of the WSPD-spanner $W$ on the leader points in Step 3 uses $O(n)$ space. $G_T$ is a dual graph on $O((d+1)n)$ leaves of $T$. Since $G_T$ has $O((d+1)n)$ edges, for storing $G_T$, $O((d+1)n)$ extra space is needed. For running $A^*$, we need $O(n)$ extra space for maintaining a priority-queue. Greedy-Path uses $O(n)$ extra space for bookkeeping. Thus, the total space requirement amounts to $O((d+1)n)$.

Fast-Sparse-Spanner is a $t$-spanner algorithm (can always produce $t$-spanners for any value of $t>1$) if $h$ is set to the diameter of $G_T$. Since $G_T$ is connected, in this case, all leaf pairs will be considered for merging in Steps 4 and 5, and consequently, $t$-paths will be ensured for every point pair in $P$. Hence, we state the following theorem without a proof.

For any integer value of $k$, if $h$ is set to the diameter of $G_T$, then Fast-Sparse-Spanner will always produce $t$-spanners for any value of $t>1$.

However, setting $h$ to the diameter of $G_T$ will make the algorithm slow for large pointsets. In Section <ref>, we present precise $t$-dependent values for $h$ used in our experiments.

While worst-case time complexities are high, our experiments suggest
that the average-case time complexities are exceptionally low. See the
discussion in Section <ref>.

§ COMPUTING THE STRETCH-FACTOR OF $H$

In this section, we present a simple algorithm, named Fast-Stretch-Factor, that can compute stretch-factor of any spanner $H$ generated by Fast-Sparse-Spanner.
Refer to Algorithm <ref>. It is a minor modification of the
Greedy-Merge-Light algorithm. It needs the quad-tree
$T$ used for constructing $H$.

Let $\Xi$ be the set of non-empty	leaves of $T$ and $X$ be all pairs of distinct leaves in $\Xi$.  When
$H$ was constructed by our algorithm  Fast-Sparse-Spanner, a
subset $M$ of  $X$ were considered for merging in Steps 4 and 5. At
that time, it was ensured
that for every leaf pair $\{\sigma_i,\sigma_j\}$ in $M$ and for every point pair $\{u \in \sigma_i,v\in \sigma_j\}$, there exists  a  $t$-path in $H$. Thus, it is enough to consider  the remaining leaf pairs in $X \setminus M$ and look for the set $\Gamma$ of point pairs (points from two different leaves) not having $t$-paths in $H$. Clearly, inside every leaf, it is impossible to have a pair that does not have a $t$-path since we have used  FG-Greedy to create local $t$-spanners inside every leaf.
However, in doing so, we do not modify $H$ (since we are computing its stretch-factor). The algorithm returns $t_H := \max(t,\max_{\{u,v\}\in \Gamma} \pi(u,v) / |uv|)$.

each $\{\sigma_i,\sigma_j\} \in X \setminus M$

Let $P_i, P_j$ be the two pointsets inside the leaves $\sigma_i,\sigma_j$, respectively

Sort $P_i$ based on their distances from the leader point   $\ell_{\sigma_j}$

Sort $P_j$ based on their distances from the leader point $\ell_{\sigma_i}$

$\texttt{bridges} = \emptyset$
the edge $\{\ell_{\sigma_i},\ell_{\sigma_j}\} \in H$
$\texttt{bridges} = \texttt{bridges} \cup \{\{\ell_{\sigma_i},\ell_{\sigma_j}\}\}$

each $u \in P_i$
each $v \in P_j$
$\nexists$ $x\curly y \in \texttt{bridges}$ such that $\dfrac{t\cdot |ux| + |x\curly y| + t \cdot |yv|  } {|uv| }\leq t$
the path $u \curly v$ returned by Greedy-Path$(H,u,v)$ is a $t$-path between $u,v$
$\texttt{bridges}  = \texttt{bridges} \cup \{u \curly v\}$

the shortest path $\pi(u,v)$ between $u,v$ returned by $A^*$ is a $t$-path

$\texttt{bridges}  = \texttt{bridges} \cup \{\pi(u,v)\}$

$t_H = \max\left(t_H, \dfrac{|\pi(u,v)| }{ |uv|}\right)$;

return $t_H$

Next, we derive the asymptotic time and space complexities for Fast-Stretch-Factor in Theorem <ref>.

For fixed values of $h$ and $k$,
Fast-Stretch-Factor runs in $O(n^3\log n)$ expected time and uses $O(n)$ extra space.

There are $\Theta(n^2)$ non-empty leaf pairs in $X \setminus M$. If $M$ is maintained using a hash-table, it takes $O(1)$ expected time to whether a pair $\{\sigma_i,\sigma_j\} \in M$. Every merging maintains no more than $k^2$ bridges. Since Greedy-Path runs in $O(n)$ time and $A^*$ in $O(n\log n)$ time, for every pair in $X \setminus M$, we spend $O(k^4 \cdot n\log n ) =  O(n\log n)$ time to verify the existence of $t$-paths among $k^2$ pairs. The two sorting calls run in $O(k \log k) = O(1)$ time each. Hence, the total expected time taken by Fast-Stretch-Factor is $O(n^2 \cdot n\log n) = O(n^3\log n)$.

For storing the bridges found so far, $O(1)$ space is needed. Both Greedy-Path and $A^*$ calls need $O(n)$ space each.  So, the total space complexity amounts to $O(n)$.

Remarks. In this algorithm, we initialize $t_H$ with $t$. So, if the actual stretch-factor is less than $t$, it will still return $t$ as the stretch-factor.

Note that the pairs in $X \setminus M$ are faraway leaf pairs since the ones which are at most $h$ hops away from each other have already been merged while constructing $H$. So, in most cases,  contain a very few bridges which are enough to verify the existence of $t$-paths between all points pairs in $P_i \times  P_j$. Further, the $t$-paths between  faraway point pairs have a low number of edges because of the existence of the long WSPD edges in $H$. Consequently, the two path-finding algorithms, Greedy-Path and $A^*$, terminate fast. This helps our algorithm to be faster than the naive Dijkstra-based algorithm in practice that runs in $O(n^2\log n)$ time on sparse graphs. Refer to Section <ref> for experimental evidence.

§ EXPERIMENTS

We have implemented our algorithms in $17$ using the  library. Two machines with same configuration were deployed for conducting the experiments. Both of them are equipped with   processors and $32$ GB of main memory, and run .  Our code was compiled using the  compiler, invoked with  flag to achieve fast real-world speed.

Algorithms Fast-Sparse-Spanner and Fast-Stretch-Factor have
been engineered to be as fast as possible.
From , the  is used for accuracy and speed.  For a quad-tree implementation, we have used . To engineer FG-Greedy, we have used   from the   library for a robust implementation of the Dijkstra's shortest path algorithm.

For maintaining sets (where no ordering is required),  have been used.

Synthetic pointsets.
Following the strategies used in previous experimental work
[11, 51, 35, 9], we
used the following distributions for drawing random
pointsets. Refer to Fig. <ref>, for a visualization of the point distributions.

The point distributions used in our experiments.

* . The
generator was
used to generate points uniformly inside a square.

* . A set of $\sqrt{n}$ clusters placed
randomly in the plane. Each cluster contains $\sqrt{n}$ normally
distributed points (mean and standard-deviation are set to 2.0). The
coordinates were
generated using .

* . Points were
generated on a $\lceil 0.7n \rceil \times \lceil 0.7n\rceil $ unit
square grid. The value $0.7$ was
chosen arbitrarily to obtain well-spaced non-contiguous grid
points. The coordinates are integers and were
generated independently using .

* . Points were
generated inside an annulus whose outer radius is set to 500 and the inner
radius was
set to 400. We
used   to generate the coordinates.

* . Points are generated in the shape of a spiral galaxy having outer five arms [42].

* . Points were
generated using .

* . Points were
generated in the shape of five spokes.

Real-world pointsets. The following real-world pointsets were
used in our experiments.
Note that they are not known to follow any specific distribution. We removed the duplicate points from them before running the experiments.

*  [1, 9]. An $33,708$-element pointset representing cities in Burma.

*  [17, 37, 9, 35]. An $99,999$-element pointset representing random clusters at random locations.

*  [1, 37, 9, 35]: A $100,000$-city TSP instance representing a continuous-line drawing of the Mona Lisa.

*  [17, 9, 37, 35].  An $104,297$-element pointset representing the first two dimensions of a protein data-set.

*  [1, 37, 9, 35].  A $115,475$-city TSP instance representing (nearly) all towns, villages, and cities in the United States.

*  [17, 37, 9, 35].  An $168,435$-element pointset representing differential coordinates of the map of Europe.

Values for $t',k,h$. Refer to Algorithm <ref>. We
$t'$ for WSPD-spanner construction on the leader points of the
non-empty leaves. In our experiments, we found that $t'=1.25$ suffices
when $1.1\leq t \leq 1.25$. However, when $t < 1.1$ or $t>1.25$, we
used $t'=t$.

Left: Determining an appropriate value for $k$; Right: Determining appropriate values for $h$ for different values of $t$ used in our experiments.

To find a suitable value for $k$, we ran an experiment with a $128K$-element pointset, drawn from the  distribution. We varied $k$ from $500$ to $4000$, using increments of $500$. Refer to Fig. <ref> (left). We observed that after $k=2500$, runtime increases substantially along with memory usage, and quite surprisingly, average-degree did not decrease, as one would expect. This motivated us to fix $k$ to $2500$ in our algorithm. We note that as $k$ increases, every execution of FG-Greedy gets more resource-intensive. Further, every execution of Greedy-Merge (Algorithm <ref>) and Greedy-Merge-Light (Algorithm <ref>) used in Steps 4 and 5 also gets more expensive in terms of time and memory usage.  As $k$ approaches $n$, the output spanner converges to an actual greedy-spanner.

For choosing appropriate values for $h$, we  generated seven $1M$-element pointsets, one from each of the seven  synthetic distributions. Then, we ran  Fast-Sparse-Spanner on them by varying $h$ from $1$ to $7$. See Fig. <ref> (right). In this case, the failure rate is defined as the percentage of samples (out of $7$) where the desired stretch-factors were not achieved. For every $t \in \{1.05,1.1,1.25,2\}$ and $h \in \{1,2,\ldots,7\}$, we measured the  failure rates. The objective is to find the $h$-values that give us $0\%$ failure rates. Using the experimental data, the optimum $h$-values for the four stretch-factors $1.05,1.1, 1.25,2$ were set to $6,5,3,1$, respectively.

Stretch-factors of the  Fast-Sparse-Spanner graphs.  Surprisingly,
even though Fast-Sparse-Spanner only strives to get as close
as possible to the desired stretch-factor, it never failed to achieve
the	stretch-factor in our experiments.  To gain confidence, we ran our algorithm using pointsets drawn from the seven distributions. In this experiment, nine values of $n$ were chosen from  $\{1K,2K,\ldots,128K,256K\}$ and $t$  from  $\{1.05,1.1,1.25,2\}$. For every value of $n$, we have used $100$ samples. Thus in total, we conducted $7 \cdot 9 \cdot 100 \cdot 4 = 25,200$ trials and measured the stretch-factors of the output spanners using Fast-Stretch-Factor. Our algorithm  never missed the target stretch-factor. We have also performed a similar experiment on the aforementioned real-world pointsets using the four stretch-factors and observed that Fast-Sparse-Spanner could construct graphs with the desired stretch-factors.

Comparison with the popular algorithms. We have compared Fast-Sparse-Spanner with seven other popular algorithms mentioned in Section <ref>. See Fig. <ref>. For every value of $n \in \{1K,2K,\ldots,128K\}$, we have drawn $10$ samples from the  distribution. The stretch-factor was fixed at $1.1$ throughout the experiment.

In this experiment, $n \in \{1K,2K,\ldots,128K\}$, $t=1.1$. The pointsets were drawn from the  distribution. Left: Average execution times for the eight algorithms; Middle: Average-degrees of the spanners generated by the eight algorithms; Right: Average-degrees of the spanners generated by the eight algorithms without the WSPD-spanners. The WSPD-spanner algorithm crashed after $n=64K$.

The Approximate-Greedy algorithm needs a bounded-degree spanner in its Step 1 [25]. In the experimental paper [31] by Farshi and Gudmundsson, the authors have used Sink-spanner in Step 1 since such spanners are bounded-degree. In our experiments, we have also used $\Theta$-Graph (although not guaranteed to be bounded-degree) in its place to observe how it performs. Thus, we have used two versions of the same algorithm, Approximate-Greedy-$\Theta$ and Approximate-Greedy-Sink.

In terms of speed,  we found that WSPD-spanner algorithm was the fastest, but it ran out of memory after $n=64K$ since it tends to generate near-complete graphs for low values of $t$. Our algorithm was the second fastest, and Bucketing turned out to be the slowest.

Average-degrees of the WSPD-graphs skyrocketed even for values of $n \leq 64K$. In this regard, Bucketing came out as the winner, and Fast-Sparse-Spanner was very close to Bucketing. The other six algorithms generated graphs that have substantially more average-degrees across all values of $n$.
Both in terms of speed and average-degree, Approximate-Greedy-$\Theta$ always beat Approximate-Greedy-Sink everywhere.
Hence, it can be concluded that Bucketing is our closest competitor when average-degree is the primary concern.

Experimental comparison with Bucketing. Since the goal is to construct
sparse spanners with low stretch-factors, we have used the following
four values of $t$: $1.05,1.1,1.25,2$ for comparing
Fast-Sparse-Spanner with Bucketing. The comparison is done based on runtime, memory usage,  average-degree, and diameter. Since Bucketing runs very slow, we have used $3$ trials for every value of $n$ and computed average runtimes, memory usages, average-degrees, and diameters. But for Fast-Sparse-Spanner, we have used $10$ trials since it runs fast to completion.

* Runtime and memory usage. Fast
execution speed and low memory usage are two desired
characteristics of spanner construction algorithms when one tries to
construct low-stretch-factor spanners on large pointsets. Refer to
the top rows in the Figs. <ref>,<ref>,<ref>,<ref>,<ref>,<ref>,,<ref> for runtime
and the bottom rows for memory usage comparisons for pointsets drawn from the seven pointset distributions (Fig. <ref>). The legends can be found in Fig. <ref>.
In the synthetic pointset trials, we varied $n$ from $1K$ to $128K$, with increments by a factor of $2$.

In our
experiments with both synthetic and real-world pointsets, we found
that Fast-Sparse-Spanner is remarkably faster than our
closest competitor Bucketing as  $n$ gets larger. For $128K$-element   pointsets, the observed speedups are approximately $ 85, 41, 12 , 2$, for the four stretch-factors $1.05,1.1,1.25,2$, respectively.
Among the seven distributions used in our experiments, the highest speedups are observed for the
and  pointsets when $t=1.05$. For $n=128K$, the observed speedup is
more than $1000$, in both the cases. For low values of $t$ such as $1.05,1.1,1.25$, our
algorithm is substantially faster than Bucketing.

However, with the increase in $t$, Bucketing caught up with Fast-Sparse-Spanner (while still being noticeably slower). Overall, we observed that our algorithm behaved almost like a linear-time algorithm in practice.

On the memory usage front, Fast-Sparse-Spanner beat Bucketing almost everywhere for large values of $n$. However, in some cases such as the  distribution and $t=2$,  Bucketing used less memory but not by much.

Single-threaded runtimes (in minutes), memory usages (in MB), and average-degrees for Fast-Sparse-Spanner, where $n=10^6$.

Next we investigate the performance (time, memory and
average degree) of Fast-Sparse-Spanner for
different input point distributions and for different
values of stretch factors.

Refer to Fig. <ref>

for the case when $n=10^6$. We found that even for such large pointsets and stretch-factor as low as $1.05$, our algorithm finished within two hours for all the distributions and used a reasonable amount of extra memory (at most $1.8$ GB). When $n=10^6$, Bucketing took around five days (not shown in the table) to construct a $1.1$-spanner on a pointset drawn from  and used $5.8$ GB of main memory. In contrast, our algorithm took just $55$ minutes and used $\approx 1.3$ GB of main memory, making it roughly $130$ times faster. For  pointsets, for $n=10^6$, our algorithm took a mere $13$ minutes to construct a $1.05$ spanner and used around $715$ MB of extra memory. Note that Bucketing took more than $20$ hours even for a $128K$-element  pointset. Among the seven distributions, when $n=10^6$, our algorithm ran fastest on  pointsets and slowest on  and  pointsets.

Our algorithm beat Bucketing for all the real-world pointsets used in our experiments in terms of speed. See Fig. <ref>. Once again, we observed that Bucketing struggled to complete with Fast-Sparse-Spanner for low values of $t$. For the used real-world pointsets, the best speed-up of $\approx 136$ was observed in the case of  ($n=168,435$), when $t=1.1$. In most cases, our algorithm used less memory than Bucketing. We note that for some of the real-world pointsets viz., , , and  and certain values of $t$, Bucketing used less memory than Fast-Sparse-Spanner but the differences are quite tolerable in practice. The higher memory usages are marked in bold in Fig <ref>.

Therefore, we conclude  that irrespective of the geometry of the input pointset, Fast-Sparse-Spanner is substantially faster than Bucketing in practice and in most cases tends to use much less amount of runtime memory.

Runtime (in minutes), memory usage (in MB), average-degree (Avg($\Delta$)), and diameter ($\diameter$) in the case of real-world pointsets  are shown.  In this table, Prl-Fast-Sparse-Spanner stands for  Parallel-Fast-Sparse-Spanner; the columns $1T,2T,4T$ show the runtimes for $1$ thread (same as the fourth column in this table), $2$ threads, and $4$ threads, respectively.

* Average-degree (Avg($\Delta$)).
For low stretch-factor spanners, low average-degree is desired since it helps to optimize per-node communication cost. With the decrease in $t$, average-degree tends to increase since more edges must be placed to ensure $t$-paths between all vertex pairs in a spanner. Greedy-spanners are unbeatable in this aspect and there is no other practical algorithm (fast and memory-efficient) that can produce spanners having near-greedy average-degree. In our experiments, we found that average-degrees of the spanners produced by Fast-Sparse-Spanner are not far from that of the greedy-spanners. For average-degree comparisons for synthetic pointsets, refer to the Figs. <ref>,<ref>,<ref>,<ref>,<ref>,<ref>,<ref> and Fig. <ref> for real-world pointsets.

For $t=1.05,1.1,1.25,2$, we observed that the average-degrees of the spanners produced by Fast-Sparse-Spanner never exceeded $14.2, 9.7, 6, 3.75$, respectively. The observed differences in average-degrees of the spanners produced by the two algorithms never exceeded a unit. For smaller pointsets, the difference is much less.
It shows that our algorithm produced near-greedy size spanners everywhere. In the case of synthetic pointsets, the average-degrees of the spanners did not increase by much even when $n$ is set to $1M$ (see Fig. <ref>), corroborating the fact that our algorithm is efficient when it comes to placements of edges. For example, when $t$ was set to $1.1$, the average-degree of the spanner produced by Bucketing was observed to be $9.08$ and that of the spanner produced by our algorithm was $9.64$.  We believe that such small increments in average-degrees should be acceptable in most practical applications given that Bucketing runs for days and our algorithm runs to completion in a couple of hours (much faster when multiple threads are used) on $1M$-element pointsets.
Further, Fast-Sparse-Spanner   tends to place fewer edges with the increase of $t$, a desired property of spanner construction algorithms.

Step 2 in our algorithm, where greedy-spanners are constructed inside every non-empty leaf, contributed the most in average-degree of the final spanner.
We found that the number of edges placed in steps 3,4 was very low and contributed marginally to average-degree. Step 5 did not put any edges for some pointsets, such as those drawn from the  distribution.
To illustrate, for $128K$-element  pointsets, step 2 added $\approx 8.46$ to the average-degree of the final spanner and steps 3, 4, 5 added $\approx 0.23,0.65,0$, respectively. In contrast, for $128K$-element  pointsets, the contributions are approximately $8.5,0.1,0.01,0.002$, for steps 2, 3, 4, 5, respectively. Empty spaces (holes) inside the convex hull of the pointsets force our algorithm to place a few edges (compared to $n$) in step 5 for ensuring $t$-paths between distant point pairs whose parent leaves are within $h$ hops of each other in $G_T$, separated by a void (a sequence of empty leaves).

* Diameter ($\diameter$). As mentioned earlier,  the diameter of a graph $H$ is defined as the length (number of edges) of the longest shortest path among all vertex pairs in $H$. In our case, the presence of long WSPD edges (placed in Step 3) gives us the benefit of low diameter in most cases. We found that the diameter of the spanners produced by our algorithm is substantially less than the greedy-spanners in most cases, without any intolerable increase in average-degrees. See Fig. <ref> for the diameters obtained for  real-world points and Figs. <ref>,<ref>,<ref>,<ref>,<ref>,<ref>,<ref> for the synthetic distributions.

In the case of real-world pointsets, Fast-Sparse-Spanner could always beat Bucketing. In this regard, we observed the best performance for the  pointset ($n=100K$),  $t=1.1$; the diameter of the spanner produced by Bucketing was $6.5$ times more than that of the one constructed by Fast-Sparse-Spanner. Further, our algorithm placed just $\approx 2.8\%$ extra edges, was $\approx14$ times faster, and used $\approx 50\%$ less memory.

For the , , , , and  distributions, Fast-Sparse-Spanner always produced spanners having considerably lower diameter for all the four values of stretch-factors. However, we noticed that for the  and  distributions when $t$ was set to $1.05$, Bucketing beat our algorithm by a considerable difference. In those two cases, the WSPD edges could not help much in reducing the diameter of the spanners. However, with the increase in $t$, our algorithm took the lead. For all the seven distributions, the differences in diameters of the spanners generated by the two algorithms increased with the increase in $t$ ($\geq 1.1$); Fast-Sparse-Spanner generated spanners with far less diameter than the ones constructed by Bucketing. This is expected since greedy-spanners tend to have shorter edges when $t$ is increased. In contrast, Fast-Sparse-Spanner still places long WSPD edges in the spanners, no matter how large $t$ is,  thereby vastly reducing the diameters of the spanners.

Efficacy of Fast-Stretch-Factor.  We compare the Dijkstra-based stretch-factor measurement algorithm (run from every vertex) with our algorithm Fast-Stretch-Factor.  Refer to Fig. <ref>. We have used two values of $n$, $256K$ and $1M$.  Further, we fixed $t$ to $1.1$ in our experiment since the same trend was observed for all values of $t$.

Fast-Stretch-Factor vs Dijkstra: $t$ was fixed to $1.1$ and $4$ threads were used.  Top: $n=256K$; Bottom: $n=10^6$. The reported times are in minutes.

Fast-Stretch-Factor is easily parallelizable since the unmerged leaf pairs can be considered independently in the main for-loop. Similarly, the Dijkstra-based algorithm can be parallelized by executing the shortest path computations from every vertex in parallel.
As both are easily parallelizable, we have used $4$ threads in our comparison experiment. It is clearly evident that in both cases ($n=256K,1M$), Fast-Stretch-Factor outperformed the Dijkstra-based algorithm. For instance, for a $1.1$-spanner, constructed on a $1M$-element  pointset by Fast-Sparse-Spanner, the Dijkstra-based algorithm took $1318.25$ minutes (around $22$ hours), whereas Fast-Stretch-Factor took just $46.39$ minutes making our algorithm $\approx 28.42$ times faster.  The best speedup of $\approx 89.5$ was achieved for the  distribution, $n=1M$, where Fast-Stretch-Factor could finish up within $10$ minutes but Dijkstra took around $14.8$ hours.

The main reason behind the speed of our algorithm is the avoidance of unnecessary graph explorations done from every vertex of the input spanner by the Dijkstra-based algorithm. Fast-Sparse-Spanner explores the spanner in a restrictive way using Greedy-Path and $A^*$. Further, it works only with the leaf pairs which were not considered during the spanner construction in Fast-Sparse-Spanner and tries to reuse the Greedy-Path and $A^*$ paths to check for the existence of $t$-paths between point pairs from two different leaves. Further, due to the long edges of $W$ in $H$, we found that the Greedy-Path and $A^*$ executions ran to completion fast. For instance, for a $1.1$-spanner generated by Fast-Sparse-Spanner on a $1M$-element  pointset, Greedy-Path and $A^*$ explored approximately $1690$ and $10700$ vertices on average. Note that these numbers are much less than $1M$. Further, Greedy-Path was successful $\approx 92.6\%$ of the times in finding $t$-paths. Consequently, in practice, for every pair, the time taken to compute $t$-paths is much less than linearithmic, as assumed in Theorem <ref>. As a result, Fast-Stretch-Factor behaves like a quadratic-time algorithm in practice and could easily beat Dijkstra everywhere.

Parallel Fast-Sparse-Spanner. Parallelization of Fast-Sparse-Spanner is straightforward. In Step 1, we construct local greedy-spanners in parallel. We always found that the runtimes of steps 1 and 2 are a minuscule of the total runtime. So, we did not parallelize it. The mergings in steps 4 and 5 can be easily executed in parallel. In our experimental results, we set the number of threads to $1,2$ and $4$.
We have leveraged  for parallelization. To see
thread-dependent runtimes, refer to Fig. <ref>
for real-world pointsets and
Figs. <ref>,<ref>,<ref>,<ref>,<ref>,<ref>,<ref>
for the synthetic distributions.

Speed-ups are remarkably close to the number of threads used.

However, we point out that with the increase in threads, the memory usage increases because of the per-thread space requirements for the mergings in Steps 4 and 5. For instance, on a $128K$-element  pointset, our implementation consumed approximately $ 189, 285,  473$ MB of main memory for $1,2,4$ threads, respectively.

Time and memory usage comparisons for the  distribution.

Time and memory usage comparisons for the  distribution.

Time and memory usage comparisons for the  distribution.

Time and memory usage comparisons for the  distribution.

Time and memory usage comparisons for the  distribution.

Time and memory usage comparisons for the  distribution.

Time and memory usage comparisons for the  distribution.

Average-degree comparisons for the  distribution.

Average-degree comparisons for the  distribution.

Average-degree comparisons for the  distribution.

Average-degree comparisons for the  distribution.

Average-degree comparisons for the  distribution.

Average-degree comparisons for the  distribution.

Average-degree comparisons for the  distribution.

Diameter comparisons for the  distribution.

Diameter comparisons for the  distribution.

Diameter comparisons for the  distribution.

Diameter comparisons for the  distribution.

Diameter comparisons for the  distribution.

Diameter comparisons for the  distribution.

Diameter comparisons for the  distribution.

Multithreaded runtimes for the   distribution; $T$ stands for thread.

Multithreaded runtimes for the   distribution; $T$ stands for thread.

Multithreaded runtimes for the   distribution; $T$ stands for thread.

Multithreaded runtimes for the   distribution; $T$ stands for thread.

Multithreaded runtimes for the   distribution; $T$ stands for thread.

Multithreaded runtimes for the   distribution; $T$ stands for thread.

Multithreaded runtimes for the   distribution; $T$ stands for thread.

§ WHY IS OUR ALGORITHM FAST IN PRACTICE?

Section <ref> provides evidence that
Fast-Sparse-Spanner behaves like a near-linear-time
algorithm in practice, suggesting that the average-case time
complexity is nearly linear for most distributions.

The running time of Fast-Sparse-Spanner (see
Theorem <ref>) is $O(n\log n + n (d^2+f(n) ))$, where
$O(n\log n)$ is the time taken to construct the WSPD-spanner $W$, $d$
is the depth of the quad tree $T$, and $f(n)$ is the time taken to
compute a $t$-path between two vertices in $H$. In the worst-case
scenario, $f(n) = O(n\log n)$ since $A^*$ is a modified version of
Dijkstra, thus making the overall worst-case time complexity to be
$O(n^2\log n)$ since there are $O(n)$ mergings
(Corollary <ref>).

We argue that in the case of uniform distributions (e.g.,
), $A^*$ is likely to be fast. Our intuition is
based on the observation that neighboring leaves of the quad-tree are
likely to be of almost the same size for the uniform distribution,
making the dual graph of small degree, thus making the number of
vertices visited by $A^*$ within $h$ hops to be small. Thus, on the
average, we expect $f(n) = O(1)$. We conjecture that the average-case
time complexity of Fast-Sparse-Spanner is $O(n\log n)$ with
linear additive terms.

Consistent with out intuition above,
in our experiments, we observed that the construction of $W$ takes a negligible fraction of the total runtime. For instance, on a $1M$-element  pointset and $t=1.1$, the construction of $W$ took just $35$ milliseconds, and the whole spanner construction took around $55$ minutes (Fig <ref>).
Next, we always found that $d$ was never more than $20$ (quad-trees for  pointsets had the highest depths in our experiments). As a result, the term $d^2n$ tends to be linear in practice. Further, we found that both $A^*$ and Greedy-Path always explored a low number of vertices in $H$ (much less than $n$). For the same pointset, on average, Greedy-Path explored approximately $35$ and $417$ vertices in steps $4$ and $5$, respectively. $A^*$ explored approximately $38$ and $2210$ vertices on average in the two steps, respectively. The early terminations were possible owing to the long WSPD edges placed by the algorithm. Further, we noticed that Greedy-Path was successful $\approx 83.75\%$ of the times in finding $t$-paths. As a result, the number of $A^*$ calls was much less compared to the number of Greedy-path calls.
It resulted in fast $t$-path computations inside Greedy-Merge and Greedy-Merge-Light. Consequently, $f(n)$ was slow-growing in practice. The above observations account for the linear runtime behavior of Fast-Sparse-Spanner.

§ CONCLUSIONS

Our experiments show that Fast-Sparse-Spanner is remarkably
faster than Bucketing and uses substantially less memory in
most cases. The spanners produced by  Fast-Sparse-Spanner were found to have near-greedy average-degree, and low diameter.
Surprisingly, in our rigorous
testing, we found that the produced spanners always had the desired stretch-factors. It would be interesting to extend the presented ideas to higher dimensions for future work.

Acknowledgment. We are grateful to Kevin Buchin, one of the authors of the Bucketing algorithm [5], for generously sharing their Bucketing code with us and communicating over email.

[1]

[2]
Abu-Affash, A. K., Bar-On, G., and Carmi, P.
$\delta$-greedy $t$-spanner.
Computational Geometry 100 (2022), 101807.

[3]
Agarwal, P. K., Klein, R., Knauer, C., Langerman, S., Morin, P., Sharir,
M., and Soss, M.
Computing the detour and spanning ratio of paths, trees, and cycles
in 2d and 3d.
Discrete & Computational Geometry 39, 1-3 (2008), 17–37.

[4]
Alewijnse, S., Bouts, Q. W., ten Brink, A. P., and Buchin, K.
Computing the greedy spanner in linear space.
Algorithmica 73, 3 (2015), 589–606.

[5]
Alewijnse, S., Bouts, Q. W., Ten Brink, A. P., and Buchin, K.
Distribution-sensitive construction of the greedy spanner.
Algorithmica 78, 1 (2017), 209–231.

[6]
Althöfer, I., Das, G., Dobkin, D., Joseph, D., and Soares, J.
On sparse spanners of weighted graphs.
Discrete & Computational Geometry 9, 1 (1993), 81–100.

[7]
Alzoubi, K., Li, X.-Y., Wang, Y., Wan, P.-J., and Frieder, O.
Geometric spanners for wireless ad hoc networks.
IEEE Transactions on parallel and Distributed Systems 14, 4
(2003), 408–421.

[8]
Anderson, F., Ghosh, A., Graham, M., Mougeot, L., and Wisnosky, D.
An interactive tool for experimenting with bounded-degree plane
geometric spanners (media exposition).
In 37th International Symposium on Computational Geometry (SoCG
2021) (2021), Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

[9]
Anderson, F., Ghosh, A., Graham, M., Mougeot, L., and Wisnosky, D.
Bounded-degree plane geometric spanners in practice.
Journal of Experimental Algorithmics (JEA) To appear (2023).

[10]
Arya, S., Mount, D. M., and Smid, M.
Dynamic algorithms for geometric spanners of small diameter:
Randomized solutions.
Computational Geometry 13, 2 (1999), 91–107.

[11]
Bentley, J. J.
Fast algorithms for geometric traveling salesman problems.
ORSA Journal on computing 4, 4 (1992), 387–411.

[12]
Borradaile, G., Le, H., and Wulff-Nilsen, C.
Greedy spanners are optimal in doubling metrics.
In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on
Discrete Algorithms (2019), SIAM, pp. 2371–2379.

[13]
Bose, P., Carmi, P., Farshi, M., Maheshwari, A., and Smid, M.
Computing the greedy spanner in near-quadratic time.
Algorithmica 58, 3 (2010), 711–729.

[14]
Bose, P., Gudmundsson, J., and Morin, P.
Ordered theta graphs.
Computational Geometry 28, 1 (2004), 11–18.

[15]
Bose, P., Gudmundsson, J., and Smid, M.
Constructing plane spanners of bounded degree and low weight.
Algorithmica 42, 3 (2005), 249–264.

[16]
Bose, P., and Smid, M.
On plane geometric spanners: A survey and open problems.
Computational Geometry 46, 7 (2013), 818–830.

[17]
Bus, N., Mustafa, N. H., and Ray, S.
Practical and efficient algorithms for the geometric hitting set
Discrete Applied Mathematics 240 (2018), 25–32.

[18]
Callahan, P. B., and Kosaraju, S. R.
Faster algorithms for some geometric graph problems in higher
In SODA (1993), vol. 93, pp. 291–300.

[19]
Callahan, P. B., and Kosaraju, S. R.
A decomposition of multidimensional point sets with applications to
$k$-nearest-neighbors and $n$-body potential fields.
Journal of the ACM (JACM) 42, 1 (1995), 67–90.

[20]
Chan, T. M.
More algorithms for all-pairs shortest paths in weighted graphs.
SIAM Journal on Computing 39, 5 (2010), 2075–2089.

[21]
Chandra, B., Das, G., Narasimhan, G., and Soares, J.
New sparseness results on graph spanners.
International Journal of Computational Geometry & Applications
5, $01n02$, 125–144.

[22]
Cheng, S.-W., Knauer, C., Langerman, S., and Smid, M.
Approximating the average stretch factor of geometric graphs.
Journal of Computational Geometry 3, 1 (2012), 132–153.

[23]
Clarkson, K.
Approximation algorithms for shortest path motion planning.
In Proceedings of the nineteenth annual ACM symposium on Theory
of computing (1987), pp. 56–65.

[24]
Czumaj, A., and Zhao, H.
Fault-tolerant geometric spanners.
In Proceedings of the nineteenth annual symposium on
Computational geometry (2003), pp. 1–10.

[25]
Das, G., and Narasimhan, G.
A fast algorithm for constructing sparse euclidean spanners.
International Journal of Computational Geometry & Applications
7, 04 (1997), 297–315.

[26]
De Berg, M., Cheong, O., Van Kreveld, M., and Overmars, M.
Computational geometry: introduction.
Computational geometry: algorithms and applications (2008),

[27]
Dumitrescu, A., and Ghosh, A.
Lattice spanners of low degree.
Discrete Mathematics, Algorithms and Applications 8, 03 (2016),

[28]
Dumitrescu, A., and Ghosh, A.
Lower bounds on the dilation of plane spanners.
International Journal of Computational Geometry & Applications
26, 02 (2016), 89–110.

[29]
Eppstein, D., and Khodabandeh, H.
On the edge crossings of the greedy spanner.
In 37th International Symposium on Computational Geometry
(2021), vol. 12, p. 37.

[30]
Evans, W., and de Arruda Siaudzionis, L. M.
On path-greedy geometric spanners.
Computational Geometry 110 (2023), 101948.

[31]
Farshi, M., and Gudmundsson, J.
Experimental study of geometric $t$-spanners.
Journal of Experimental Algorithmics (JEA) 14 (2010), 1–3.

[32]
Farshi, M., and Hosseini, S. H.
Visualization of geometric spanner algorithms.
In 32nd International Symposium on Computational Geometry (SoCG
2016) (2016), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[33]
Filtser, A., and Solomon, S.
The greedy spanner is existentially optimal.
SIAM Journal on Computing 49, 2 (2020), 429–447.

[34]
Finkel, R. A., and Bentley, J. L.
Quad trees a data structure for retrieval on composite keys.
Acta informatica 4, 1 (1974), 1–9.

[35]
Friederich, R., Ghosh, A., Graham, M., Hicks, B., and Shevchenko, R.
Experiments with unit disk cover algorithms for covering massive
Computational Geometry 109 (2023), 101925.

[36]
Gao, J., Guibas, L. J., Hershberger, J., Zhang, L., and Zhu, A.
Geometric spanner for routing in mobile networks.
In Proceedings of the 2nd ACM international symposium on Mobile
ad hoc networking & computing (2001), pp. 45–55.

[37]
Ghosh, A., Hicks, B., and Shevchenko, R.
Unit disk cover for massive point sets.
In International Symposium on Experimental Algorithms (2019),
Springer, pp. 142–157.

[38]
Ghosh, A., Shariful, F., and Wisnosky, D.
Visualizing wspds and their applications (media exposition).
In 38th International Symposium on Computational Geometry (SoCG
2022) (2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

[39]
Gudmundsson, J., Levcopoulos, C., and Narasimhan, G.
Fast greedy algorithms for constructing sparse geometric spanners.
SIAM Journal on Computing 31, 5 (2002), 1479–1500.

[40]
Gudmundsson, J., Levcopoulos, C., Narasimhan, G., and Smid, M.
Approximate distance oracles for geometric spanners.
ACM Transactions on Algorithms (TALG) 4, 1 (2008), 1–34.

[41]
Hart, P. E., Nilsson, N. J., and Raphael, B.
A formal basis for the heuristic determination of minimum cost paths.
IEEE transactions on Systems Science and Cybernetics 4, 2
(1968), 100–107.

[42]
A 2d procedural galaxy with c++, Mar 2014.

[43]
Kanj, I., Perkovic, L., and Turkoglu, D.
Degree four plane spanners: Simpler and better.
Journal of Computational Geometry 8, 2 (2017), 3–31.

[44]
Keil, J. M.
Approximating the complete euclidean graph.
In Scandinavian Workshop on Algorithm Theory (1988),
Springer, pp. 208–213.

[45]
Klein, R., Knauer, C., Narasimhan, G., and Smid, M.
On the dilation spectrum of paths, cycles, and trees.
Computational Geometry 42, 9 (2009), 923–933.

[46]
Le, H., and Solomon, S.
Truly optimal euclidean spanners.
SIAM Journal on Computing, 0 (2022), FOCS19–135.

[47]
Le, H., and Than, C.
Greedy spanners in euclidean spaces admit sublinear separators.
In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA) (2022), SIAM, pp. 3287–3310.

[48]
Marble, J. D., and Bekris, K. E.
Asymptotically near-optimal planning with probabilistic roadmap
IEEE Transactions on Robotics 29, 2 (2013), 432–444.

[49]
Narasimhan, G., and Smid, M.
Approximating the stretch factor of euclidean graphs.
SIAM Journal on Computing 30, 3 (2000), 978–989.

[50]
Narasimhan, G., and Smid, M.
Geometric spanner networks.
Cambridge University Press, 2007.

[51]
Narasimhan, G., and Zachariasen, M.
Geometric minimum spanning trees via well-separated pair
Journal of Experimental Algorithmics (JEA) 6 (2001), 6–es.

[52]
Rao, S. B., and Smith, W. D.
Approximating geometrical graphs via “spanners” and
In Proceedings of the thirtieth annual ACM symposium on Theory
of computing (1998), pp. 540–550.

[53]
Russel, D., and Guibas, L.
Exploring protein folding trajectories using geometric spanners.
In Biocomputing 2005. World Scientific, 2005, pp. 40–51.

[54]
Sigurd, M., and Zachariasen, M.
Construction of minimum-weight spanners.
In Algorithms–ESA 2004: 12th Annual European Symposium, Bergen,
Norway, September 14-17, 2004. Proceedings 12 (2004), Springer,
pp. 797–808.

[55]
Smid, M.
The weak gap property in metric spaces of bounded doubling dimension.
Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the
Occasion of his 60th Birthday (2009), 275–289.

[56]
Soares, J.
Approximating euclidean distances by small degree graphs.
Discrete & Computational Geometry 11, 2 (1994), 213–233.

[57]
Sommer, C.
Shortest-path queries in static networks.
ACM Computing Surveys (CSUR) 46, 4 (2014), 1–31.

[58]
Toth, C. D., O'Rourke, J., and Goodman, J. E.
Handbook of discrete and computational geometry.
CRC press, 2017.

[59]
Wulff-Nilsen, C.
Computing the maximum detour of a plane geometric graph in
subquadratic time.
Journal of Computational Geometry 1, 1 (2010), 101–122.

[60]
Xia, G.
The stretch factor of the delaunay triangulation is less than 1.998.
SIAM Journal on Computing 42, 4 (2013), 1620–1659.


Methods

In this section we describe our novel LLM-powered framework for the collection
and classification of stance detection data on social media. An overview of
our pipeline can be found in Figure pipeline. We first outline our Data
Collection process, describing source data from r/covidlonghaulers. Then, we
detail how we use LLMs to accelerate data curation via Claim Identification.
Finally, we describe our methods of Data Annotation and prompting LLMs for
Stance Detection of online health texts.
../table_figure_tex/figures/stance_pipeline LLM-in-the-Loop Data Curation

Data Source: We scrape 2388 posts from the subreddit r/covidlonghaulers
between the dates 03/01/2023, 03/31/2023. We choose this subreddit as (i) it
is timely (created in July, 2020), (ii) popular (over 50k members as of
December 2023) and (iii) focuses on medical topics, including symptoms, and
treatment, unlike several other subreddits focusing on political topics
related to COVID/Long COVID (LC). Given that we aim to focus our analysis on
the opinions of emerging LC topics, we filter the samples to only include
posts with either the “Research” or “Article” flairsA flair is a tag that
categorizes the type of post.A flair is a tag that categorizes the type of
post.as they share emerging LC-related information from peer-reviewed
literature, online news articles, blog posts and other online content (e.g.,
TikTok videos, New York Times, National Institutes of Health, Bloomberg, CNN).
After filtering for Research/Article posts, we have 202 unique posts. From
this subset, we aim to annotate the stance of comments with respect to post
titles which express claims found in emerging long COVID articles and
research.

Data Processing for Claim Identification While posts with Research/Article
flairs on Reddit refer to emerging medical research, it is often the case that
the claim made in the referenced article is not present in the post title.
Even when claims are present, such information can be implicit and may require
extensive human effort for annotation. Many prior works have avoided the issue
of claim identification by manually-curating claims covidlies, glandt-
etal-2021-stance. However, we wish to model the stance of pairs of online
health texts on emerging claims, requiring a more automated approach to post
title claim identification. Towards this end, we explore the capacity of LLMs
to perform claim identification — the task of identifying if a post title
contains an explicit or implicit health claim. Note that our dataset is unique
in that we allow claims to be implicit, as explicit claim mentions are often
assumed in prior works faramarzi2023claim, covidlies, glandt-etal-2021-stance.

We formulate claim identification as a binary classification problem, where a
post either contains an implicit/explicit claim (Yes), or does not (No).
Example explicit and implicit claims can be found in Figure fig:example_data.
We randomly sample and annotate K=9 post titles not used in LC-Stance for in-
context learning of LLMs on claim identification. This leaves 193/202
remaining posts with Article/Research flairs suitable for LLM-powered claim
identification. LLMs are well-suited to our task due to the lack of large-
scale training data for claim identification in the online health space and
their strong capacity to elicit implicit information in texts
Huang-2023-IsChatGPT. Thus demonstration of LLMs performance on claim
identification has significant implications for curating domain-specific
claim-driven datasets.

After claim identification, we are left with 96/193 posts suitable for
annotation for stance, i.e., the post titles contain a claim. Next we focus on
creating (claim, stance) tuples from these posts. To ensure that comments are
in reference to the post content and not other comments, we only consider top-
level comments for consideration in LC-Stance. In total, there are 742 first-
level comments across these 96 posts. We additionally filter deleted comments,
empty comments and comments from Reddit-bots. We also remove posts where the
title was incorrectly labeled by LLMs as a claim even when the title did not
contain any claim. After filtering, we are left with 679 comments and 74
posts, as some posts got removed due to the above mentioned filtering. From
this set, we annotate a random subset of 400 title-comment pairs to produce
LC-Stance, where each pair represents a users opinion on a given health claim.

Dataset Statistics

A summary of our dataset statistics can be found in Table table:dataset. LC-
Stance contains 74 unique Reddit post titles, with an average of 5.4 annotated
comments per title. Of the 74 titles, 45 contain explicit claims, 29 contain
implicit claims. Titles are on average 14 words long, as where comments are on
average 48 words long. Unlike Twitter, Reddit comments have no character
restrictions, thus LC-Stance is unique in comparison to related works as it
requires the modeling longer user-generated texts. For reference, in Figure
fig:text_length we compare the distribution of post comments in LC-Stance in
terms of word length with tweets from COVIDLies, a twitter-based stance
dataset. On average, LC-Stance contains longer samples than COVIDLies and
contains a number of significantly longer samples which will help highlight
model capacity to process longer online health texts.

Preparing claim identification test set: We pair the 74 unique titles in LC-
Stance with 76 titles that contain no claim to form a binary classification
test set for claim identification. The 76 claimless titles are on average 11
words long, with a max word length of 53.

Data Annotation for Stance Detection: Each (title, comment) pair was annotated
by at least one of the authors, who spent significant efforts to understand
relevant background literature on long-COVID, as well as familiarizing
themselves with common themes on the r/covidlonghaulers community. Samples
were annotated using an iterative annotation process, with frequent reference
to authentic information sources and discussion with other annotators.

We note that the choice to use author annotation was necessary for high-
quality data annotation in this task as we found mTurk-based crowd-sourced
annotation to be frequently incorrect. Specifically, we used a subset of 100
random samples from our 400 sample dataset. Each sample was annotated by three
different mTurk workers, and we used majority votes to decide the final label.
It results in 33% of outputs being errors (i.e. wrong stance labels). The poor
performance of crowd-sourced annotation is due to their limited knowledge in
this topic and lack of incentives to spend additional time to resolve
potential confusion and/or lack of knowledge. LC-Stance is thus not suitable
for use with crowd sourcing platforms.

We hope the consideration taken in our annotation process motivates future
work to consider if a task is “crowd-sourceable” as reliance on crowd workers
for domain-specific tasks may produce low-quality labels.

While our method ensures that LC-Stance contains high-quality annotation, it
is limiting in terms of dataset size, which is subject to future work.
However, we note that our dataset size is on-par with related works on LLM
evaluation and benchmarking such as Big Bench Hard (BBH)
suzgun2022challenging,srivastava2022beyond, the subset of the popular Big
Bench dataset with highly challenging LLM evaluation sets. The largest
evaluation set in BBH, for example, contains only 250 test samples. Thus, LC-
Stance contains enough samples for reliable testing of LLMs on this task.

LLM-powered Stance Detection

Prior works have highlighted the difficulty of obtaining large-scale training
data for stance detection from online health communities covidlies. Existing
solutions to this problem often leverage Natural Language Inference (NLI) data
to build zero-shot classifiers covidlies, however such data is both out-of-
domain and built for sentence-level tasks. We thus thoroughly investigate the
scope of zero-shot, few-shot, and chain-of-thought LLM prompting strategies on
the LC-Stance dataset. We believe LLMs are well-suited to model LC-Stance for
the following reasons. (i) As shown in chae2023large, LLMs show strong zero-
shot performance on social media-based text classification tasks. (ii) Texts
in LC-Stance can be upwards of 544 words long. Thus the capacity of LLMs to
model long texts Wang-2023-Document makes them well-suited to deal with
lengthy posts common to Reddit. (iii) LLMs have shown to substantially
outperform text encoders in various domain-specific tasks gatto2023text, thus
they have strong potential to perform well in online health text modeling.
(iv) LLMs have demonstrated strong ability to identify implicit semantics of
texts Huang-2023-IsChatGPT, thus making them well-suited to model implicit
claims in LC-Stance. Please refer to the supplementary materials to review
prompts used in our LLM experiments.

LLM Evaluation Setup Our evaluation on LLMs for the curation and
classification of LC-Stance aim to address the two key research questions
(RQs). We evaluate three different LLMs for each RQ: Llama2-7b
touvron2023llama, GPT-3.5, and GPT-4. We believe this to be a representative
set of LLMs as both small open-source models like Llama2 and large closed
domain models like GPT-3.5 and GPT-4. Also, GPT-3.5 and GPT-4 are larger than
most of the contemporary LLMs (thus likely to show emergent abilities) and
widely used in computational social sciences Zhu-2023-Ghatgpt.

../table_figure_tex/tables/claim_filtering ../table_figure_tex/tables/results
RQ1: Can LLMs Identify Claims in Online Health Texts? We evaluate LLMs on the
150 Reddit post titles, annotated for presence of a health claim. Recall that
74 claims in this dataset are from LC-Stance, and the remaining 76 are
claimless samples sourced to facilitate this task. We evaluate zero and few-
shot prompting of LLMs on this dataset.

We additionally benchmark the performance of an out-of-domain claim
identification model in effort to explore the need for domain-specific
solutions. Specifically, we use a publicly available DeBERTa-v2 he2021deberta
model fine-tuned on the ClaimBuster dataset arslan2020claimbuster
huggingface.co/whispAI/ClaimBuster-
DeBERTaV2huggingface.co/whispAI/ClaimBuster-DeBERTaV2, which contains
annotation for if political texts (a) contain check-worthy factual claims, (b)
unimportant factual claims, or (c) no factual claim. We consider samples
classified as either check-worthy factual claims or unimportant factual claims
as claims in our evaluation, with no factual claim mapped to no claim. We note
that while this label space differs from ours, as claims in LC-Stance can be
non-factual or unverifiable, little data similar to our problem exists in the
literature. We denote this model as ClaimDeBERTa. We report the precision,
recall, and F1 score for each experiment.

RQ2: How well Can LLMs Infer the Stance of Online Health Texts? To answer this
question, we benchmark each LLM on the LC-Stance dataset using three prompting
strategies: zero-shot, few-shot, and Chain-of-Thought (COT)
NEURIPS2022_9d560961 prompting. We demonstrate the need for LLMs on this task
by comparing model performance to prior works on zero-shot stance detection.
As demonstrated in covidlies, Natural Language Inference (NLI) models are an
effective zero-shot baseline for stance detection tasks. To evaluate NLI on
LC-Stance, we align our stance labels with NLI labels: In-Favor to Entailment,
Against to Contradiction, and Neutral to Neutral.

We evaluate three different pre-trained model types for zero-shot NLI. (i)
BART-large lewis-etal-2020-bart fine-tuned on MNLI (ii) RoBERTa-large roberta
fine-tuned on MNLI (iii) PubMedBERT Deka-2023-Multiple,pubmedbert fine-tuned
on both MNLI and MedNLI romanov-2018-lessons, which contains clinical texts
annotated for the NLI task. We additionally run a fourth baseline inspired by
covidlies, where we combine NLI models with semantic textual similarity (STS)
to improve performance. Specifically, we consider (title, comment) pairs with
less than 0.4 similarity score to be Neutral, and then allow the NLI model to
determine if the pair is more likely to be entailment (in favor) or
contradiction (against). Our experiment denoted PubMedBERT + STS uses this
inference strategy.

For each model, we report the precision, recall, and F1 score. We additionally
report the class-wise performance of each metric. Overall model performance is
determined by the Macro F1 across all classes. Note that for each LLM
experiment in the paper, we set the temperature hyperparameter to 0 for
reproducibilitiy. For open-source models such as Llama2-7b we utilize tools
such as Huggingface Transformers huggingface and
LangChainhttps://github.com/langchain-
ai/langchainhttps://github.com/langchain-ai/langchain. Experiments run locally
(i.e. not using API services) were all ran on the Google Colab computing
platform.