A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph 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.
[1] In computational geometry, the concept was first discussed by L.P. Chew in 1986,[2] although the term "spanner" was not used in the original paper.
Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric.
Spanners may be used in computational geometry for solving some proximity problems.
The most common measures are edge count, total weight and maximum vertex degree.
maximum degree (here MST denotes the weight of the minimum spanning tree).
Finding a spanner in the Euclidean plane with minimal dilation over n points with at most m edges is known to be NP-hard.
[3] Many spanner algorithms exist which excel in different quality measures.
If better weight and vertex degree is required the Greedy spanner can be computed in near quadratic time.
The basic method of construction involves partitioning the space around each vertex into a set of cones, which themselves partition the remaining vertices of the graph.
-graph defines a fixed ray contained within each cone (conventionally the bisector of the cone) and selects the nearest neighbour with respect to orthogonal projections to that ray.
The greedy spanner or greedy graph is defined as the graph resulting from repeatedly adding an edge between the closest pair of points without a t-path.
The greedy spanner was first described in the PhD thesis of Gautam Das[4] and conference paper[5] and subsequent journal paper by Ingo Althöfer et al[6].
These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction.
The greedy spanner achieves asymptotically optimal edge count, total weight and maximum vertex degree and also performs best on these measures in practice.
[7] Chew's main result was that for a set of points in the plane there is a triangulation of this pointset such that for any two points there is a path along the edges of the triangulation with length at most
The result was applied in motion planning for finding reasonable approximations of shortest paths among obstacles.
by choosing the separation parameter of the well-separated pair decomposition accordingly.