Greedy geometric spanner

<p>In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, a greedy geometric spanner is an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> whose distances approximate the <a href="/facts/Euclidean_distance/9qDoQKQe">Euclidean distances</a> among a <a href="/facts/Finite_set/za1newlP">finite set</a> of points in a <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a>. The vertices of the graph represent these points. The edges of the spanner are selected by a <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a> that includes an edge whenever its two endpoints are not connected by a short path of shorter edges. The greedy spanner was first described in the PhD thesis of <a href="/facts/Gautam_Das_(computer_scientist)/0o16Exd8">Gautam Das</a> and conference paper and subsequent journal paper by <a href="/facts/Ingo_Alth%25C3%25B6fer/q4W391hk">Ingo Althöfer</a> et al. These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction.
</p><p>Greedy geometric spanners have bounded <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>, a linear total number of edges, and total weight close to that of the <a href="/facts/Euclidean_minimum_spanning_tree/yu6atHA6">Euclidean minimum spanning tree</a>. Although known construction methods for them are slow, fast <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a> with similar properties are known.
</p>

Greedy geometric spanner open-in-new

Greedy geometric spanner