Proof by induction on n
, the number of points in our set.
Our base is when \(n=2\). The points will be connected. They must be each-other's closest point in the relevant segment: there are no other points. As they are connected the distance between any pair of points (that is, the only pair of points) is equal to the euclidean distance which is less than the stretch factor for any given \(t>1\).
Assume that \(G(t)\) is a t-spanner for \(n-1\) points.
RTP: \(G(t)\) is a t-spanner for \(n\) points.
Let k
be the point added as part of our inductive step. Let \(p(i,j)\) refer to the length of the t-path connecting i and j. We adopt the following strategy for constructing an i,j
t-path. Assume WLOG we start from i
. At every step, we choose the edge whose end-point lies in the same segment as j
.
For all pair of points \(i,j \ |\ i\neq k, j\neq k\), the spanner-property holds by our inductive hypothesis. By adding k
we have not removed edges, so if there was a spanner path before there is still.
We now move onto the pairs of points containing k
. Let us refer to one such arbitrary pair as i
,k
. We refer to the path as \(i,v_1\dots,v_{-2},j,k\).
We have that \(p(i,k) = p(i,j) + |jk|\). Clearly \(j\neq k\), hence by our inductive hypothesis \(p(i,j)\leq t\cdot |ij|\) (1).