Let S be a set of n points in the plane, and let t>1 be a real number. A t-spanner is a sparse graph having the points of S as its vertices, such that for any two points p and q in S, there is a path between them of length at most t times the Euclidean distance between p and q.
Spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges. In many applications of spanners, it is important that the spanner possess a number of additional properties, such as low total edge weight, bounded degree, and low diameter. Such spanners have much better properties than minimum spanning trees, which have been used extensively to approximate the complete Euclidean graph.
In this talk, I will give an overview of recent results on constructing spanners.