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$.


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.

Thanks in advance.

  • $\begingroup$ 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. $\endgroup$
    – Steven
    Aug 26, 2022 at 16:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.