Geometric Spanners

Source: Geometric Approximation Algorithms

For a weighted graph with vertices , the graph distance is the weight of the shortest path from to .

Let be a set of points in . A -spanner of is a weighted graph with vertices where for all , .

Construction

Given some point set and parameter , set and compute the -WSPD of , . For each , choose some arbitrary and , and add with weight to our new graph . The resulting graph will be a -spanner of with edges.

Correctness

Inducting on the edge length of pairs in . Fix , and assume for all where , we have . By construction, there is some where and . By property of WSPD, we know , therefore

Note that , thus . By the inductive hypothesis, we have

By construction, , thus we have

Note that the last step is achieved by some simple arithmetic