Let G be the complete Euclidean graph on a given set P of n points embedded in the Euclidean plane. A geometric t-spanner on P is a geometric graph G := (P, E), a subgraph of G such that for every pair of points u, v ∈ P, the distance between them in G (the Euclidean length of a shortest path between u, v in G ) is at most t times their Euclidean distance |uv |, for some t ≥ 1. It is easy to check that G itself is a 1-spanner with Θ(n 2 ) edges. The quantity t is referred to as the stretch-factor of G . If there is no need to specify t, we simply use the term geometric spanner and assume that there exists some t for G . We say that G is plane if it is crossing-free. G is degree-k or is said to have bounded-degree if its degree is at most k. In this work, we experiment with bounded-degree plane geometric spanners. Figure 1 presents an example of such a spanner.
Bounded-degree plane geometric spanners have been an area of interest in computational geometry for a long time. Non-crossing edges make them suitable for wireless network applications where edge crossings create communication interference. The absence of crossing edges also makes them useful for the design of road networks to eliminate high-budget flyovers. Such spanners have O (n) edges (at most 3n -6 edges); as a result, they are less expensive to store and navigate. Further, shortest-path algorithms run quicker on them since they are sparse. Boundeddegree helps in reducing on-site equipment costs.
A triangulation T for a pointset P is referred to as a L 2 -Delaunay triangulation if no point in P lies inside the circumcircle of any triangle in T . Bose et al. [13] were the first to show that there always exists a plane geometric σ (π + 1)-spanner of degree at most 27 on any pointset, where σ denotes an upper bound for the stretch-factor of L 2 -Delaunay triangulations (the current best known value is σ = 1.998 due to Xia [45]). This result was subsequently improved in a long series of papers [9,12,14,16,33,34,36] in terms of degree and/or stretch-factor. Bonichon et al. [11] reduced the degree to 4 with t ≈ 156.8. Soon after this, Kanj et al. [32] improved this stretchfactor upper bound to 20 in their work. A summary of these results is presented in Table 1. This family of spanner construction algorithms has turned out to be a fascinating application of the Delaunay triangulation. Note that all these algorithms produce bounded-degree plane subgraphs of the complete Euclidean graph on P with constant stretch-factors.
The intriguing question that remains to be answered is whether the degree can be reduced to 3 while keeping t bounded; refer to the work of Bose and Smid [15,Problem 14] and Toth et al. [42,Chapter 32]. Interestingly, if one does not insist on constructing a plane spanner, Das and Heffernan [23] showed that degree 3 is always achievable. Narasimhan and Smid [39,Section 20.1] show that no degree-2 plane spanner of the infinite integer lattice can have a constant stretchfactor. Thus, a minimum degree of 3 is necessary to achieve a constant stretch-factor. If the points in P are in convex position, then it is always possible to construct a degree-3 plane geometric spanners (see [3,7,32]). From the other direction, lower bounds on the stretch-factors of plane spanners for finite pointsets have been investigated elsewhere [24,25,35,37]. In-browser visualizations of some Bounded-Degree Plane Geometric Spanners in Practice 1.1:3 [32] 4 20
The best known upper bound of σ = 1.998 for the stretch-factor of the L 2 -Delaunay triangulation [45] is used in this table for expressing the stretch-factors.
of the algorithms (those based on the L 2 -Delaunay triangulation) have been recently presented in the work of Anderson et al. [2].
In related works, the construction of plane hop spanners (where the number of hops in shortest paths is of interest) for unit disk graphs has been considered [6,19,26].
The most notable experimental work for geometric spanners is done by Farshi and Gudmundsson [27]. The authors engineered and experimented with some of the well-known geometric spanners construction algorithms published before 2009. However, the authors did not use the algorithms considered in this work in their experiments. Planarity and bounded-degree are important concerns in geometric network design. Hence, we found it motivating to implement the 11 algorithms (refer to Table 1) meant to construct bounded-degree plane geometric spanners. Further, asymptotic runtimes and various theoretical bounds do not always do justice in explaining the real-world performance of algorithms, especially in computational geometry, because of heavy floating-point operations needed for various geometric calculations. Experiments reveal their realworld performance. We note that a unique aspect of the family of bounded-degree plane spanner construction algorithms is that users cannot specify an arbitrary value of t and/or degree for spanner construction. It is a deviation from many standard spanner algorithms; see elsewhere [12,39] for a review of such algorithms. This makes experiments with them even more interesting.
Our Contributions. First, we experimentally compare the aforementioned 11 bounded-degree plane spanner construction algorithms by implementing them carefully in C++ using the popular CGAL library [41] and running them on large synthetic and real-world pointsets. The largest pointset contains approximately 1.9 million points. For broader uses of these sophisticated algorithms, we share the C++ implementations via GitHub. The comparisons are performed based on their runtime, degree, stretch-factor, and lightness of the generated spanners. We present a brief overview of the algorithms implemented and our experimental results in Sections 2 and 4, respectively. The findings of our experimental study are presented in Section 5.
Second, in doing experiments with spanners, we found that stretch-factor measurement turns out to be a severe bottleneck when n is large. To address this, we have designed EstimateStretch-Factor, a fast algorithm that can estimate the stretch-factor of a given spanner (not necessarily plane). In our experiments, we found that it could estimate stretch-factors with high accuracy for the class of geometric spanners dealt with in this work. It was considerably faster than the naive Dijkstra-based exact stretch-factor measurement algorithm in practice. To our knowledge, no such practical algorithm exists in the literature. Section 3 presents a description of this algorithm.
Every algorithm designed to date for constructing bounded-degree plane geometric spanners relies on some variant of Delaunay triangulation. The rationale behind this is that such triangulations are geometric spanners [10,21,22,45] and are plane by definition. As a result, the family of plane spanner construction algorithms considered in this work has turned out to be a fascinating application of Delaunay triangulation. It is essential to know that Delaunay triangulations have unbounded degrees and cannot be used as bounded-degree plane spanners.
In this section, we provide a brief description for each of the 11 algorithms considered in this work. Appropriate abbreviations using the authors' names and dates of publication are used for naming purposes. Since most of these algorithms are involved, we urge the reader to refer to the original papers for a deeper understanding and correctness proofs. For visualizing some of these algorithms, we recommend the interactive in-browser applet developed by us (see [2]). To observe variations in spanner construction between the algorithms, see Appendix A.1.
In these algorithms, the surrounding of every input point is frequently divided into multiple cones (depending on the algorithm) for carefully selecting edges from the Delaunay triangulation used as the starting point. In our pseudocodes, the cone i of point u, considered clockwise, is denoted by C u i . A triangulation T of a pointset P is said to be an L 2 -Delaunay triangulation of P if no point in P lies inside the circumcircle of any triangle in T . Eight of the 11 algorithms use L 2 -Delaunay triangulation as the starting point. The remaining 3 algorithms use either L ∞ or T D-Delaunay triangulations, as described later in this section. In the following, n denotes the size of the input pointset:
• BGS05: Bose et al. [13]: This was the first algorithm that can construct bounded-degree plane spanners using the classic L 2 -Delaunay triangulation. First, a Delaunay triangulation DT of P is constructed. Next, a degree-3 spanning subgraph SG of DT is computed that contains the convex hull of P and is a (possibly degenerate) simple polygon with P as its vertex set. The polygon is then transformed into a simple non-degenerate polygon Q. The vertices of Q are processed in an order that is obtained from a breadth-first order of DT , then Delaunay edges are carefully added to Q. After computing the triangulation and the reverse low-degree ordering, at every vertex u, δ = 2π /α Yao cones are initialized such that the closest unprocessed triangulation neighbor falls on a cone boundary and occupies both cones as the short edge, which is added to the spanner. In the remaining cones, the closest unprocessed neighbor of u in each cone is added. In all cones, special edges between pairs of neighbors of u are added to the spanner if both neighbors are unprocessed. BGHP10 first extracts a degree-9 subgraph from the T D-Delaunay triangulation that has a stretch-factor of 6. Then using some local modifications, the degree is reduced from 9 to 6 but the stretch-factor remains unchanged. Refer to Algorithm 9. It uses internally Algorithms 10 through 15. In this algorithm, charge(u, i) maps vertex u ∈ DT and a cone i of u to the number of edges charged to the cone, initialized to 0 in the beginning. The algorithm runs in O (n log n) time, as shown by the authors.
• KPX10: Kanj et al. [33]: For every vertex u in the L 2 -Delaunay triangulation, its surrounding is divided into k ≥ 14 cones. In every nonempty cone of u, the shortest Delaunay edge incident on u is selected. After this, a few additional Delaunay edges are also selected using some criteria based on cone sequences. Algorithm 16 presents a complete description of this algorithm with the technical details. When k is set to 14, degree-14 plane spanners are generated having a stretch-factor of 1.998(1 + 2π 14 cos(π /14) ) ≈ 2.9. Note that out of the 11 algorithms we have implemented in this work, this algorithm gives the best theoretical guarantee on the stretch-factor (see Table 1). KPX10 runs in O (n log n) time.
Bounded-Degree Plane Geometric Spanners in Practice 1.1:9
ALGORITHM 11: i-distant(w, i) In each wide sequence (a sequence of exactly three consecutive edges incident to a vertex whose overall angle is at least 4π /5) around u, select the edges of the sequence;
Partition the remaining space surrounding u not in a wide sequence into a minimum number of disjoint cones of maximum angle π /5;
In each nonempty cone, select the shortest edge incident to u;
In each empty cone, let ux and uy be the incident DT edges on u clockwise and counterclockwise, respectively, from the empty cone;
If either ux or uy is selected, then select the other edge (in case it has not been selected); otherwise, select the longer edge between ux and uy breaking ties arbitrarily; 8 end 9 return all edges selected by both incident vertices;
• BCC12-7, BCC12-6: Bose et al. [12]: The authors present two algorithms in their paper.
Whereas previous algorithms used strategies involving iterating over the vertices one-byone, this algorithm takes the approach of iterating over the edges of the Delaunay triangulation in order of non-decreasing length to query agreement among the vertices for bounding degrees. BCC12-7, the simpler of the two, produces 1.998(1 + √ 2) 2 ≈ 11.6-spanners with degree 7. However, BCC12-6 constructs 11.998( Let v be the last point in Q ; From the L ∞ -Delaunay triangulation of P, a directed L ∞ -distance-based Yao graph --→ Y ∞ 4 is constructed: the space around every point p ∈ P is divided into four disjoint 90 • cones and then for each non-empty cone, and a directed edge going out of p is placed between p and its closest neighbor in the cone according to the L ∞ -distance, breaking ties arbitrarily. xand y-axes after translating the point to the origin. Each cone has an associated charge, which can be 0, 1, or 2. The algorithm labels certain edges as follows. Each edge will be an anchor or a non-anchor and weak or strong. Further, each edge may have an additional label of start-of-odd-chain-anchor. A weak anchor chain is a path w 0 , w 1 , w 2 , . . . ,w k of maximal length consisting of weak anchors such that the cone of each edge (w.r.t. the source vertex) alternates between some i and i + 2. Canonical edges are edges between consecutive vertices in the ordered neighborhood of a vertex u in a common cone i. An edge (u, v) is said to be dual if there are two or more edges of --→ Y ∞ 4 incident to cone i of u and cone i + 2 of v.
Let j be the cone of v where (u, v) is charged; • BHS18: Bose et al. [14]. This algorithm produces a plane degree-8 spanner with stretch-factor at most 1.998(1+ 2π 6 cos(π /6) ) ≈ 4.4 using the L 2 -Delaunay triangulation and Θ-graph. However, the authors do not present any runtime analysis of their algorithm. In BHS18, the space around every point p is divided into six cones and oriented such that a boundary lies on the xaxis after translating p to the origin. The algorithm starts with the L 2 -Delaunay triangulation DT , then, in order of non-decreasing bisector distance, each edge is added to the spanner if the cones containing it are both empty. For each edge added here, certain canonical edges will also be carefully added to the spanner. Refer to Algorithm 30.
1 Notations. The bisector-distance [pq] between p and q is the distance from p to the orthogonal projection of q onto the bisector of C p i where q ∈ C p i . Let {q 0 , q 1 , . . . , q d -1 } be the sequence of all neighbors of p in DT in consecutive clockwise order. The neighborhood N p with apex p is the graph with the vertex set {p, q 0 , q 1 , . . . ,q d -1 } and the edge set {{q j , q j+1 }} ∪ {{q j , q j+1 }}, 0 ≤ j ≤ d -1, with all values mod d. The edges {{q j , q j+1 }} are called canonical edges.
Measuring exact stretch-factors of large graphs is a tedious job, and also is for geometric spanners. Although many algorithms exist in the literature for constructing geometric spanners, nothing is known about practical algorithms for computing stretch-factors of large geometric spanners. It is a severe bottleneck for conducting experiments with large spanners since the stretch-factor is considered a fundamental quality of geometric spanners. For any spanner (not necessarily geometric) on n vertices, its exact stretch-factor can be computed in O (n 2 log n + n|E|) time by running the folklore Dijkstra algorithm (implemented using a Fibonacci heap) from every vertex, and in Θ(n 3 ) time by running the classic Floyd-Warshall algorithm. Note that the Dijkstra-based algorithm runs O (n 2 log n) time for plane spanners since the number of edges is O (n). Both of these are very slow in practice. However, the latter has a quadratic space-complexity and is unusable when n is large. Consequently, they are practically useless when n is large. Stretch-factor estimation of large geometric graphs appears to be a far cry despite theoretical studies on this problem (see [1,20,28,38,44]). We believe these algorithms are either involved from an algorithm engineering standpoint or rely on well-separated pair decomposition [18], which may potentially slow down practical implementations due to the large number of well-separated pairs needed by those algorithms. This has motivated us to design a practical algorithm, named EstimateStretchFactor, which gives a lower bound on the actual stretch-factor of any geometric spanner (not necessarily plane). However, we will consider the universe of plane geometric spanners as the input domain in this work. To our knowledge, we are not aware of any such algorithm in the literature. Refer to Algorithm 33, which takes as input an n-element pointset P and a geometric graph G, constructed on P. The underlying idea of our algorithm is as follows. We observe that most geometric spanners are well constructed, meaning it is likely that far away points (having many hops in the shortest paths between them) have low detour ratios (ratio of the length of a shortest path to that of the Euclidean distance) between them and the worst-case detour is achieved by point pairs that are a few hops apart. Note that stretch-factor of a graph is the maximum detour ratio over all vertex pairs. To capture closeness, we use the L 2 -Delaunay triangulation constructed on P as the basis. For every point p ∈ P, we start a breadth-first traversal on the Delaunay triangulation DT . At every level, we compute the detour ratios in G from p to all the points in that level. If a worse detour ratio is found in the current level compared to the worst found in the previous level, we continue to the next level; otherwise, the process is terminated. For finding detour ratios in G, we use the folklore Dijkstra algorithm since computation of shortest paths are required. In our algorithm, π G (p, q) denotes a shortest path between the points p, q ∈ P in G and |π G (p, q)| its total length. The detour between p, q in G can be easily calculated as |π G (p, q)|/|pq|. The current level is denoted by h. It is assumed that the neighbors of p in G are at level 1. For efficiency reasons, we do not restart Bounded-Degree Plane Geometric Spanners in Practice 1.1:19
the Dijkstra at every level of the breadth-first traversal; instead, we save our progress from the previous level and continue after that.
To our surprise, we found that for the class of spanners used in this work, EstimateStretchFactor returned exact stretch-factors almost every time. The precision error was very low whenever it failed to compute the exact stretch-factor. Further, our algorithm can be parallelized very easily by spawning parallel iterations of the foreach loop. Apart from the L 2 -Delaunay triangulation (which can be constructed very fast in practice), it does not use any advanced geometric structure, making it fast in practice. We present our experimental observations for this algorithm in Section 4.3.
We have implemented the algorithms in GNU C++17 using the CGAL library [41]. The machine used for experiments is equipped with an AMD Ryzen 5 1600 (3.2 GHz) processor and 24 GB of main memory, and runs Ubuntu Linux 20.04 LTS. The g++ compiler was invoked with -O3 flag to achieve fast real-world speed. From CGAL, the Exact_predicates_inexact_constructions_kernel is used for accuracy and speed.
All 11 algorithms considered in this work use one of the following three kinds of Delaunay triangulation as the starting point: L 2 , T D, and L ∞ . For constructing L 2 and L ∞ -Delaunay triangulations, the CGAL::Delaunay_triangulation_2 and CGAL::Segment_Delaunay_graph_Linf_2 implementations have been used, respectively. As of now, a T D-Delaunay triangulation implementation is not available in the CGAL. It was pointed out by Chew [22] that such triangulations can be constructed in O (n log n) time. However, no precise implementable algorithm was presented. But luckily, it is shown in the work of Bonichon et al. [8] that T D-Delaunay triangulation of a pointset is the same as its 1 2 -Θ graph. We leveraged this result and used the O (n log n) time CGAL::Construct_theta_graph_2 implementation for constructing the T D-Delaunay triangulations. For faster speed, the input pointsets are always sorted using CGAL::spatial_sort before constructing Delaunay triangulations on them.
In our experiments, we have used both synthetic and real-world pointsets, as described next.
We have used the following eight distributions to generate synthetic pointsets for our experiments. The selection of these distributions are inspired by the ones used elsewhere [4,5,29,30,40] for geometric experiments. Figure 2 allows us to visualize these eight distributions:
(1) uni-square: Points were generated uniformly inside a square of side length of 1,000 using the CGAL::Random_points_in_square_2 generator. (2) uni-disk: Points were generated uniformly inside a disc of radius 1,000 using the CGAL::Random_points_in_disc_2 generator. (3) normal-clustered: A set of 10 normally distributed clusters placed randomly in the plane.
Each cluster contains n/10 normally distributed points (mean and standard deviation were set to 2.0). We have used std::normal_distribution<double> to generate the point coordinates. (4) normal: This is the same as normal-clustered except that only one cluster was used.
(5) grid-contiguous: Points were generated contiguously on a √ n × √ n square grid using the CGAL::points_on_square_grid_2 generator. (6) grid-random: Points were generated on a 0.7n × 0.7n unit square grid. The value 0.7 was chosen arbitrarily to obtain well-separated non-contiguous grid points. The coordinates of the generated points are integers and were generated independently using std::uniform_int_distribution. (7) annulus: Points were generated inside an annulus whose outer radius was set to 1,000 and the inner radius to 800. We have used std::uniform_real_distribution to generate the coordinates. ( 8) galaxy: Points were generated in the shape of a spiral galaxy having outer five arms (see [31]).
For seeding the random number generators from C++, we have used the Mersenne twister engine std::mt19937. Since some of the algorithms assume that no two points must have the same value xor y-coordinates, the generated pointsets were perturbed using the CGAL::perturb_points_2 function with 0.0001, 0.0001 as the two required parameters.
The following real-world pointsets were obtained from various publicly available sources. We have removed duplicate points (wherever present) from the pointsets. The main reason behind the use of such pointsets is that they do not follow the popular synthetic distributions. Hence, experimenting with them is beneficial to see how the algorithms perform on them:
• burma: 33,708-element pointset representing cities in Burma [29,43].
• birch3: 99,801-element pointset representing random clusters at random locations [17,30].
• monalisa: 100,000-city TSP instance representing a continuous-line drawing of the Mona Lisa [29,30,43]. • KDDCU2D: 104,297-element pointset representing the first two dimensions of a protein dataset [17,29,30]. • usa: 115,475-city TSP instance representing (nearly) all towns, villages, and cities in the United States [29,30,43]. • europe: 168,896-element pointset representing differential coordinates of the map of Europe [17,29,30]. • wiki: 317,695-element pointset of coordinates found in English language Wikipedia articles (source: https://github.com/placemarkt/wiki_coordinates). • vlsi: 744,710-element pointset representing a very large-scale integration chip [43].
Bounded-Degree Plane Geometric Spanners in Practice 1.1:21 Fig. 3. The plot legends.
• china: 808,693-element pointset representing cities in China [17,29,30].
• world: 1,904,711-element pointset representing all locations in the world that are registered as populated cities or towns, as well as several research bases in Antarctica [29,30,43]. • nyctaxi: 2,728,717-element pointset representing Yellow Cab pickup locations in New York
City in 2016 [29] (source: https://www.kaggle.com/c/nyc-taxi-trip-duration).
We have seen in Section 3 that it is quite challenging to measure stretch-factor of large spanners. This motivated us to design and use the EstimateStretchFactor algorithm in our experiments for estimating stretch-factors of the generated spanners. In the following, we compare Estimat-eStretchFactor with Dijkstra's algorithm (run from every vertex) and show that for the eight distributions it is not only much faster than Dijkstra but can also estimate stretch-factors of plane spanners with high accuracy.
The main reason behind the fast practical performance of EstimateStretchFactor is early terminations of the breadth-first traversals (one traversal per vertex), which in turn makes Dijkstra run fast to find the shortest paths to the vertices in all the levels. We have noticed in our experiments that the pair that achieves the stretch-factor for a bounded-degree plane spanner are typically a few hops away and pairwise stretch-factors (ratio of detour between two vertices to that of their Euclidean distance) drop with the increase in hops. Consequently, the breadth-first traversals terminate very early most of the time.
The total number of pointsets used in this comparison experiment is 11 • 8 • 10 • 5 = 4, 400 since there are 11 algorithms, eight distributions, and 10 distinct values of n (1K, 2K, . . . , 10K ), and five samples were used for every value of n. Out of these, the number of times EstimateStretch-Factor has failed to return the exact stretch-factor is just 8. Thus, the observed failure rate is ≈ 0.18%. Interestingly, in the cases where EstimateStretchFactor failed to compute the exact stretch-factor, the largest observed error percentage between the exact stretch-factor (found using Dijkstra) and the stretch-factor returned by it is just ≈ 0.15. This gave us the confidence that our algorithm can be safely used to estimate stretch-factor of large spanners. Refer to Figure 5. As is evident from these graphs, EstimateStretchFactor is substantially faster than Dijkstra everywhere. Henceforth, we use EstimateStretchFactor (Algorithm 33) to estimate the stretch-factors of the spanners in our experiments.
We compare the 11 implemented algorithms based on their runtime, degree, stretch-factor, and lightness of the generated spanners.
In the interest of space, we avoid legend tables everywhere in our plots. Since the legends are used uniformly everywhere, we present them here for an easy reference (Figure 3).
For synthetic pointsets, we varied n from 10K to 100K. For every value of n, we have used five random samples to measure runtimes and the preceding characteristics of the spanners. In the case of real-world pointsets, we ran every one of them five times and computed the average time taken.
In our experiments, we found that BGHP10 and KPT17 were considerably slower than the other algorithms considered in this work. The reason behind this is slow construction of T D-Delaunay triangulations. Figure 4 represents an illustration. When n = 100K, both took more than 150 seconds to finish. In contrast, the other nine algorithms took less than 10 seconds. Since real-world speed is an important factor for spanner construction algorithms, we do not consider them further in our runtime comparisons:
• Runtime: Fast execution speed is highly desired for spanner construction on large pointsets.
We present the runtimes for all eight distributions in Figure 6. As explained earlier, we have excluded BGHP10 and KPT17 from these plots since they are considerably slower than the other nine algorithms. Interestingly, we found that the relative performance of these algorithms is independent of the point distributions. We further observed that not only are these algorithms slow because of the time taken to construct T D-Delaunay triangulation, but interestingly, their non-Delaunay steps are even slower than the other algorithms. Thus, this means that even if the construction of T D-Delaunay triangulation is engineered more efficiently, BGHP10 and KPT17 will still be the slowest in practice. For all eight distributions, we found that BKPX15 was much slower than the others. This is mainly due to the time taken to construct L ∞ -Delaunay triangulation. Among the ones that use L 2 -Delaunay triangulations, BGS05 was the slowest due to the overhead of creation of temporary geometric graphs needed to control the degree and stretch-factor of the output spanners. Refer to Section 2 to see more details on this algorithm. The fastest algorithms are KPX10, BSX09, LW04, and KX12. The main reason behind their speedy performance is fast construction of L 2 -Delaunay triangulations and lightweight processing of the triangulations for spanner construction. The BHS18, BCC12-7, and BCC12-6 algorithms came out quite close to the preceding four algorithms. Note that these three algorithms also use L 2 -Delaunay triangulation as the starting point. The same observations hold for the real-world pointsets used in our experiments. The table presented in Figure 9 presents the runtimes in seconds.
• Degree: Refer to Figure 7. In the tables, Δ denotes the theoretical degree upper bound, as claimed by the authors of these algorithms; max Δ observed denotes the maximum degree observed in our experiments; avg Δ observed denotes the observed average degree; and avg Δ vertex denotes the observed average degree per vertex. In our experiments, we found that spanners generated by BGS05, LW04, and BSX09 have degrees much less than the degree upper bounds derived by the authors. Although it cannot be denied that there could be special examples where these upper bounds are actually achieved, the maximum degrees achieved in our experiments are 14, 11, and 9, respectively. Note that the theoretical degree upper bounds where the degree of the spanner generated by this algorithm exceeds 6 (in fact, it is 7 in this example). For every algorithm, we found that the average degree of the generated spanners was not far away from the maximum observed degrees. It shows that the algorithms appear to spread the edges evenly in constructing the spanners. The average degree per vertex is another way to judge the quality of the spanners. In this regard, we found that it was always between 6 and 3 everywhere and is quite reasonable for practical purposes. This shows that Bounded-Degree Plane Geometric Spanners in Practice 1.1:27 all these algorithms are very careful when it comes to the selection of spanner edges. The lowest values were achieved by BKPX15 and KPT17. For the real-world pointsets, we found similar performance from the algorithms when it comes to the degree and degree per vertex of the spanners. This is quite surprising since these real-world pointsets do not follow specific distributions. Refer to Figures 10 and11 for more details. Note that BSG05 has produced a degree-15 spanner for the vlsi pointset. In contrast, for the synthetic pointsets, the highest degree we could observe is 14. • Stretch-factor: Refer to Figure 8. In the tables, t denotes the theoretical stretch-factor, as derived by the authors of these algorithms; t max denotes the maximum stretch-factor observed in our experiments; and t avg denotes the average observed stretch-factor. Among the 11 algorithms, KPX10 has the lowest guaranteed stretch-factor-it is 2.9. The stretch-factors of the spanners generated by KPX10 are always less than 1.6, thereby making it the best among the 11 algorithms in terms of stretch-factor. In this regard, BKPX15 turned out to be the worst; the largest stretch-factor we have observed is 7.242, although it is substantially less than the theoretical stretch-factor upper bound of 156.8. Its competitor KPX17 that can also generate degree-4 plane spanners has a lower observed maximum stretch-factor-it is 5.236 (the theoretical upper bound is 20 for this algorithm). Overall, we found that the stretch-factors of the generated spanners are much less than the claimed theoretical upper bounds. This shows that the generated spanners are well constructed in practice. With the exception of BKPX15, we found that the average stretch-factors are quite close to the maximum stretchfactors. Now let us turn our attention to the real-world pointsets. Refer to Figure 12. Once again, KPX10 produced the lowest stretch-factor spanners. The stretch-factors seem quite reasonable everywhere except in the two cases of vlsi and nyctaxi pointsets when fed to BKPX15. The produced spanners have stretch-factors of 11.535 and 20.009, respectively. The latter is interesting since the lower bound example constructed by Bonichon et al. [11] for the worst-case stretch-factor of the spanners produced by BKPX15 has a stretch-factor of 7 + 7 √ 2 ≈ 16.899. The nyctaxi pointset beats this lower bound. • Lightness: The lightness of a geometric graph G on a pointset P is defined as ratio of the weight of G to that of a Euclidean minimum spanning tree on P. Since a minimum spanning tree is the cheapest (in terms of the sum of the total length of the edges) way to connect n points, lightness can be used to judge the quality of spanners. This metric is beneficial when spanners are used for constructing computer or transportation networks. Refer to Figure 8. Lightness is denoted by . With a few exceptions, we found that lightness somewhat correlates with degree. This is because using a lower number of carefully placed spanner edges usually leads to lower lightness. The spanners generated by BGS05 are always found to have the highest lightness. This is expected because of their high degrees. Although the difference in degree of the spanners generated by BGXS05 and LW04 is marginal (around 2), the difference between their lightness is substantial (approximately 6 for some cases). However, the degree-4 spanners generated by KPT17 have the lowest lightness (less than 2.9 everywhere). Interestingly, although BKPX15 generates degree-4 spanners, their lightness was found to be approximately twice that of the ones generated by KPT17. In fact, their lightness turned out to be one of the highest. This shows that KPT17 is more careful when it comes to placing long edges. The lightness of the spanners generated for real-world pointsets follows a similar trend, and we did not observe anything special. Figure 13 presents more details.
Bounded-Degree Plane Geometric Spanners in Practice 1.1:29
Remark. In our experiments, we found that the spanners' degree, stretch-factor, and lightness remained somewhat constant with the increase in n. Hence, we do not present plots for them.
Since there are various ways (speed, degree, stretch-factor, lightness) to judge the 11 algorithms, it is hard to declare the winner(s). Thus, based on our experimental observations, we come to the following conclusions (which are our recommendations as well):
• If speedy performance is the main concern, we recommend using KPX10, BSX09, LW04, or KX12. • When it comes to minimization of degree, we recommend using BCC12-7 or BHS18 since they produce spanners of reasonable degrees in practice. If degree-4 spanners are desired, we recommend using BKPX15 since KPT17 is much slower in practice. • In terms of stretch-factor, we found the KPX10 as the clear winner. This is particularly important in the study of geometric spanners since not much is known about fast construction of low stretch-factor spanners (t ≈ 1.6) in the plane having at most 3n edges. However, the spanners produced by it have higher degrees compared to the ones produced by some of the other algorithms, such as BCC12 and BHS18. • In our experiments, KPT17 produced spanners with the lowest lightnesses. But in practice, we found it to be very slow compared to the other algorithms except for BGHP10 (which is as slow as KPT17). If degree-4 spanners are not a requirement, we recommend using BHS18 or BCC12-7 since they produced spanners of reasonable lightness (less than 4 most of the time).
For the C++ implementations, refer to our GitHub repository at https://github.com/ghoshanirban/ BoundedDegreePlaneSpannersCppCode. Refer to the applet hosted at https://ghoshanirban.github. io/bounded-degree-plane-spanners/index.html for an in-browser visual experience. Bounded-Degree Plane Geometric Spanners in Practice 1.1:33
In the following, we present a 13-element pointset on which BCC12-6 fails to construct a degree-6 plane spanner. Figure A.13 presents the pointset. First, BCC12-6 creates the L 2 -Delaunay triangulation of P and initializes seven cones around every p i , oriented such that the shortest edge incident on p i falls on a boundary. See Figures A.14
ACM Journal of Experimental Algorithmics, Vol. 28, No. 1, Article 1.1. Publication date: April 2023.
end
return E ; ACM Journal of Experimental Algorithmics, Vol. 28, No. 1, Article 1.1. Publication date: April 2023.
Received 5 May 2022; revised 7 November 2022; accepted 6 December 2022 ACM Journal of Experimental Algorithmics, Vol. 28, No. 1, Article 1.1. Publication date: April 2023.