Dependable Spanners via Unreliable Edges

Sariel Har-Peled, Maria C. Lusardi

Let $P$ be a set of $n$ points in ${\mathbb{R}}^d$, and let $\epsilon ,\psi \in (0,1)$ be parameters. Here, we consider the task of constructing a $(1+\epsilon )$-spanner for $P$, wh…