# Construction of a t-spanner from a WSPD

I recently studied about this construction of a spanning graph for a set of points in $$\mathbb{R}^2$$ and I feel like I'm not really understanding why this construction should work.

First there are some required definitions:

Two sets $$A,B$$ are said to be well seperated w.r.t to $$s>0$$, if there exists some $$r\in \mathbb R$$ such that both $$A$$ and $$B$$ are contained in separate balls of radius $$r$$ $$B_A , B_B$$ and $$d(B_A, B_B) \geq sr$$.

WSPD:

Let $$S\subset \mathbb R^2$$.

$$\{\{A_1,B_1\},...,\{A_m,B_m\}\}$$ is a WSPD for $$S$$ w.r.t $$s>0$$ if $$A_i,B_i$$ are well seperated w.r.t $$s$$ and for all $$p,q\in S$$ there exists a unique $$i$$ such that $$p\in A_i, q\in B_i$$ or $$q\in A_i, p\in B_i$$.

In case something is not clear with the way I've defined things, it is all stated here

The algorithm that uses WSPD to construct a t-spanner, uses $$t=\frac{s+4}{s-4}$$,

Let $$S\subset \mathbb R^2$$ and a WSPD for $$S: \{\{A_1,B_1\},...,\{A_m,B_m\}\}$$ let $$G$$ be a graph on $$S$$ with $$E=\{\{a_i,b_i\}: a_i\in A_i, b_i\in B_i, 1\leq i\leq m\}$$.

Basically what it does is consider a WSPD, and for every pair it picks an edge for the spanner arbitrarily. What I don't understand is why is it not possible for the output graph to have even isolated vertices? I mean, couldn't it be that some point $$q\in S$$ will never be picked for an edge?

Any insights on this algorithm would be appreciated, especially on what I asked with regards to it not having isolated vertices.

• Why do you say that the spanner picks one edge for every pair? Given a pair $\{A_i, B_i\}$, all pairs $\{a_i, b_i\}$ with $a_i \in A_i$ and $b_i \in B_i$ satisfy the condition in the definition of $E$, therefore they should all be included. Aug 26, 2022 at 16:37