Geometric spanner

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a <a href="/facts/Weighted_graph/W0MqKkyE">weighted graph</a> over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the <a href="/facts/Stretch_factor/SIAdGBaB">stretch factor</a> or dilation factor of the spanner.
In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper.
The notion of <a href="/facts/Graph_spanner/W0MqKkyE">graph spanners</a> has been known in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>: t-spanners are <a href="/facts/Spanning_subgraph/W0MqKkyE">spanning subgraphs</a> of graphs with similar dilation property, where distances between graph vertices are defined in <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">graph-theoretical terms</a>. Therefore geometric spanners are graph spanners of <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a> <a href="/facts/Graph_embedding/IyBA3ttM">embedded in the plane</a> with edge weights equal to the distances between the embedded vertices in the corresponding metric.
Spanners may be used in <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a> for solving some <a href="/facts/Proximity_problems/18F1GUcv">proximity problems</a>. They have also found applications in other areas, such as in <a href="/facts/Motion_planning/DoSPv4dB">motion planning</a>, <a href="/facts/Telecommunication_network/NFCX0STS">telecommunication networks</a>, network reliability, optimization of <a href="/facts/Roaming/SEfznzxD">roaming</a> in <a href="/facts/Mobile_network/8zA0jQJ9">mobile networks</a>, etc.

Geometric spanner open-in-new

Geometric spanner