Spanners under the Hausdorff and Fréchet Distances

Abstract

We initiate the study of spanners under the Hausdorff and Fréchet distances. We show that any $t$-spanner of a planar point-set $S$ is a $\frac{\sqrt{t^2-1}}{2}$-Hausdorff-spanner and a $\min \{\frac{t}{2},\frac{\sqrt{t^2-t}}{\sqrt{2}}\}$-Fréchet spanner. We also prove that for any $t>1$, there exist a set of points $S$ and an ${\epsilon }_1$-Hausdorff-spanner of $S$ and an ${\epsilon }_2$-Fréchet-spanner of $S$, where ${\epsilon }_1$ and ${\epsilon }_2$ are constants, such that neither of them is a $t$-spanner.