Greedy geometric spanner

<h2 id="construction">Construction</h2>
The greedy geometric spanner is determined from an input consisting a set of points and a parameter 
 
 
 
 t
 ≥
 1
 
 
 {\displaystyle t\geq 1}
 
. The goal is to construct a graph whose shortest path distances are at most 
 
 
 
 t
 
 
 {\displaystyle t}
 
 times the geometric distances between pairs of points. It may be constructed by a <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a> that adds edges one at a time to the graph, starting from an <a href="/facts/Edgeless_graph/Ro1YV0g6">edgeless graph</a> with the points as its vertices. All pairs of points are considered, in sorted (ascending) order by their distances, starting with the <a href="/facts/Closest_pair_of_points_problem/54Aw1kRV">closest pair</a>. For each pair 
 
 
 
 (
 u
 ,
 v
 )
 
 
 {\displaystyle (u,v)}
 
 of points, the algorithm tests whether the graph constructed so far already contains a path from 
 
 
 
 u
 
 
 {\displaystyle u}
 
 to 
 
 
 
 v
 
 
 {\displaystyle v}
 
 with length at most 
 
 
 
 t
 ⋅
 d
 (
 u
 ,
 v
 )
 
 
 {\displaystyle t\cdot d(u,v)}
 
. If not,
the edge 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 with length 
 
 
 
 d
 (
 u
 ,
 v
 )
 
 
 {\displaystyle d(u,v)}
 
 is added to the graph.
By construction, the resulting graph is a <a href="/facts/Geometric_spanner/yblwj8bF">geometric spanner</a> with <a href="/facts/Stretch_factor/SIAdGBaB">stretch factor</a> at most 
 
 
 
 t
 
 
 {\displaystyle t}
 
.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
A naive implementation of this method would take time 
 
 
 
 O
 (
 
 n
 
 3
 
 
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n^{3}\log n)}
 
 on inputs with 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points. This is because the considerations for each of the 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 pairs of points involve an instance of <a href="/facts/Dijkstra%2527s_algorithm/ehun88jl">Dijkstra's algorithm</a> to find a shortest path in a graph with 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 edges. It uses 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 space to store the sorted list of pairs of points. More careful algorithms can construct the same graph in time 
 
 
 
 O
 (
 
 n
 
 2
 
 
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n^{2}\log n)}
 
,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> or in space 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
A construction for a variant of the greedy spanner that uses graph clustering to quickly approximate the graph distances runs in time 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 in Euclidean spaces of any bounded dimension, and can produce spanners with (approximately) the same properties as the greedy spanners.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> The same method can be extended to spaces with bounded <a href="/facts/Doubling_space/8y92hNdN">doubling dimension</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="properties">Properties</h2>
The same greedy construction produces spanners in arbitrary <a href="/facts/Metric_space/gnBBRXtc">metric spaces</a>, but in Euclidean spaces it has good properties some of which do not hold more generally.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
The greedy geometric spanner in any metric space always contains the <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> of its input, because the greedy construction algorithm follows the same insertion order of edges as <a href="/facts/Kruskal%2527s_algorithm/sg8v1BHB">Kruskal's algorithm</a> for minimum spanning trees. If the greedy spanner algorithm and Kruskal's algorithm are run in parallel, considering the same pairs of vertices in the same order, each edge added by Kruskal's algorithm will also be added by the greedy spanner algorithm, because the endpoints of the edge will not already be connected by a path. In the limiting case when 
 
 
 
 t
 
 
 {\displaystyle t}
 
 is large enough (e.g. 
 
 
 
 t
 >
 n
 
 
 {\displaystyle t>n}
 
, where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of vertices in the graph) the two algorithms produce the same output.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
In Euclidean spaces of bounded dimension, for any constant 
 
 
 
 t
 
 
 {\displaystyle t}
 
, the greedy geometric 
 
 
 
 t
 
 
 {\displaystyle t}
 
-spanners on sets of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points have bounded <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>, implying that they also have 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 edges.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> This property does not extend even to well-behaved metric spaces: there exist spaces with bounded <a href="/facts/Doubling_space/8y92hNdN">doubling dimension</a> where the greedy spanner has unbounded vertex degree.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a><a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> However, in such spaces the number of edges is still 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
Greedy geometric spanners in bounded-dimension Euclidean spaces also have total weight at most a constant times the total weight of the <a href="/facts/Euclidean_minimum_spanning_tree/yu6atHA6">Euclidean minimum spanning tree</a>.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a><a class="footnote-ref" id="fnref:21" href="#fn:21">21</a><a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>
This property remains true in spaces of bounded doubling dimension.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Das, Gautam (1990), Approximation Schemes in Computational Geometry (doctoral dissertation), University of Wisconsin, MR 2685391, OCLC 22935858 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah (1990), "Generating sparse spanners for weighted graphs", SWAT 90, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 26–37, CiteSeerX 10.1.1.158.2241, doi:10.1007/3-540-52846-6_75, ISBN 978-3-540-52846-3, retrieved 2021-03-16 <a href="978-3-540-52846-3" target="_blank">978-3-540-52846-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José (1993), "On sparse spanners of weighted graphs", Discrete & Computational Geometry, 9 (1): 81–100, doi:10.1007/BF02189308, MR 1184695 <a href="/wiki/Ingo_Alth%C3%B6fer" target="_blank">/wiki/Ingo_Alth%C3%B6fer</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Filtser, Arnold; Solomon, Shay (2016), "The greedy spanner is existentially optimal", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), New York, NY, USA: ACM, pp. 9–17, arXiv:1605.06852, doi:10.1145/2933057.2933114, S2CID 7229289 <a href="/wiki/Symposium_on_Principles_of_Distributed_Computing" target="_blank">/wiki/Symposium_on_Principles_of_Distributed_Computing</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José (1993), "On sparse spanners of weighted graphs", Discrete & Computational Geometry, 9 (1): 81–100, doi:10.1007/BF02189308, MR 1184695 <a href="/wiki/Ingo_Alth%C3%B6fer" target="_blank">/wiki/Ingo_Alth%C3%B6fer</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bose, Prosenjit; Carmi, Paz; Farshi, Mohammad; Maheshwari, Anil; Smid, Michiel (2010), "Computing the greedy spanner in near-quadratic time", Algorithmica, 58 (3): 711–729, doi:10.1007/s00453-009-9293-4, MR 2672477, S2CID 8068690 <a href="/wiki/Jit_Bose" target="_blank">/wiki/Jit_Bose</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Alewijnse, Sander P. A.; Bouts, Quirijn W.; ten Brink, Alex P.; Buchin, Kevin (2015), "Computing the greedy spanner in linear space", Algorithmica, 73 (3): 589–606, arXiv:1306.4919, doi:10.1007/s00453-015-0001-2, MR 3411749, S2CID 253977471 <a href="/wiki/Algorithmica" target="_blank">/wiki/Algorithmica</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Das, Gautam; Narasimhan, Giri (1997), "A fast algorithm for constructing sparse Euclidean spanners", International Journal of Computational Geometry and Applications, 7 (4): 297–315, doi:10.1142/S0218195997000193, MR 1460840 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Gudmundsson, Joachim; Levcopoulos, Christos; Narasimhan, Giri (2002), "Fast greedy algorithms for constructing sparse geometric spanners", SIAM Journal on Computing, 31 (5): 1479–1500, doi:10.1137/S0097539700382947, MR 1936655 <a href="/wiki/SIAM_Journal_on_Computing" target="_blank">/wiki/SIAM_Journal_on_Computing</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Filtser, Arnold; Solomon, Shay (2016), "The greedy spanner is existentially optimal", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), New York, NY, USA: ACM, pp. 9–17, arXiv:1605.06852, doi:10.1145/2933057.2933114, S2CID 7229289 <a href="/wiki/Symposium_on_Principles_of_Distributed_Computing" target="_blank">/wiki/Symposium_on_Principles_of_Distributed_Computing</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Filtser, Arnold; Solomon, Shay (2016), "The greedy spanner is existentially optimal", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), New York, NY, USA: ACM, pp. 9–17, arXiv:1605.06852, doi:10.1145/2933057.2933114, S2CID 7229289 <a href="/wiki/Symposium_on_Principles_of_Distributed_Computing" target="_blank">/wiki/Symposium_on_Principles_of_Distributed_Computing</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José (1993), "On sparse spanners of weighted graphs", Discrete & Computational Geometry, 9 (1): 81–100, doi:10.1007/BF02189308, MR 1184695 <a href="/wiki/Ingo_Alth%C3%B6fer" target="_blank">/wiki/Ingo_Alth%C3%B6fer</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Chandra, Barun; Das, Gautam; Narasimhan, Giri; Soares, José (1995), "New sparseness results on graph spanners", International Journal of Computational Geometry and Applications, 5 (1–2): 125–144, doi:10.1142/S0218195995000088, MR 1331179 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Das, Gautam; Heffernan, Paul; Narasimhan, Giri (1993), "Optimally sparse spanners in 3-dimensional Euclidean space", Proceedings of the Ninth Annual Symposium on Computational Geometry (SoCG '93), New York, NY, USA: ACM, pp. 53–62, doi:10.1145/160985.160998 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Das, Gautam; Narasimhan, Giri (1997), "A fast algorithm for constructing sparse Euclidean spanners", International Journal of Computational Geometry and Applications, 7 (4): 297–315, doi:10.1142/S0218195997000193, MR 1460840 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Filtser, Arnold; Solomon, Shay (2016), "The greedy spanner is existentially optimal", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), New York, NY, USA: ACM, pp. 9–17, arXiv:1605.06852, doi:10.1145/2933057.2933114, S2CID 7229289 <a href="/wiki/Symposium_on_Principles_of_Distributed_Computing" target="_blank">/wiki/Symposium_on_Principles_of_Distributed_Computing</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Har-Peled, Sariel; Mendel, Manor (2006), "Fast construction of nets in low-dimensional metrics and their applications", SIAM Journal on Computing, 35 (5): 1148–1184, doi:10.1137/S0097539704446281, MR 2217141, S2CID 37346335 <a href="/wiki/Sariel_Har-Peled" target="_blank">/wiki/Sariel_Har-Peled</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Smid, Michiel H. M. (2009), "The weak gap property in metric spaces of bounded doubling dimension", in Albers, Susanne; Alt, Helmut; Näher, Stefan (eds.), Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 5760, Springer, pp. 275–289, doi:10.1007/978-3-642-03456-5_19 <a href="/wiki/Susanne_Albers" target="_blank">/wiki/Susanne_Albers</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Filtser, Arnold; Solomon, Shay (2016), "The greedy spanner is existentially optimal", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), New York, NY, USA: ACM, pp. 9–17, arXiv:1605.06852, doi:10.1145/2933057.2933114, S2CID 7229289 <a href="/wiki/Symposium_on_Principles_of_Distributed_Computing" target="_blank">/wiki/Symposium_on_Principles_of_Distributed_Computing</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Chandra, Barun; Das, Gautam; Narasimhan, Giri; Soares, José (1995), "New sparseness results on graph spanners", International Journal of Computational Geometry and Applications, 5 (1–2): 125–144, doi:10.1142/S0218195995000088, MR 1331179 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Das, Gautam; Heffernan, Paul; Narasimhan, Giri (1993), "Optimally sparse spanners in 3-dimensional Euclidean space", Proceedings of the Ninth Annual Symposium on Computational Geometry (SoCG '93), New York, NY, USA: ACM, pp. 53–62, doi:10.1145/160985.160998 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Das, Gautam; Narasimhan, Giri (1997), "A fast algorithm for constructing sparse Euclidean spanners", International Journal of Computational Geometry and Applications, 7 (4): 297–315, doi:10.1142/S0218195997000193, MR 1460840 <a href="/wiki/Gautam_Das_(computer_scientist)" target="_blank">/wiki/Gautam_Das_(computer_scientist)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Filtser, Arnold; Solomon, Shay (2016), "The greedy spanner is existentially optimal", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC '16), New York, NY, USA: ACM, pp. 9–17, arXiv:1605.06852, doi:10.1145/2933057.2933114, S2CID 7229289 <a href="/wiki/Symposium_on_Principles_of_Distributed_Computing" target="_blank">/wiki/Symposium_on_Principles_of_Distributed_Computing</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
</ol>

Greedy geometric spanner open-in-new

Greedy geometric spanner