Local Geometric Spanners

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set $$P$$ and a region R belonging to a family $${\mathcal {R}}$$ , we define $$G \cap R$$ to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t $${\mathcal {R}}$$ is a geometric graph G on $$P$$ such that for any region $$R \in {\mathcal {R}}$$ , the graph $$G\cap R$$ is a t-spanner for $$K(P) \cap R$$ , where $$K(P)$$ is the complete geometric graph on P. For any set $$P$$ of n points and any constant $$\varepsilon > 0$$ , we prove that $$P$$ admits local $$(1 + \varepsilon )$$ -spanners of sizes $$O(n \log ^{6} n)$$ and $$O(n \log n)$$ w.r.t axis-parallel squares and vertical slabs, respectively. If adding Steiner points is allowed, then local $$(1 + \varepsilon )$$ -spanners with O(n) edges and $$O(n \log ^2 n)$$ edges can be obtained for axis-parallel squares and disks using O(n) Steiner points, respectively.