Local Spanners Revisited

• Published in: arXiv.org 2022-01
• Main Authors: Ashur, Stav, Har-Peled, Sariel
• Format: Article
• Language: English
• Subjects: Algorithms; Graph theory; Rectangles
• ISSN: 2331-8422

\(\newcommand{\Emph}[1]{{\it{#1}}} \newcommand{\FF}{\mathcal{F}}\newcommand{\region}{\mathsf{r}}\newcommand{\restrictY}[2]{#1 \cap {#2}}\)For a set of points \(P \subseteq \mathbb{R}^2\), and a family of regions \(\FF\), a \(\Emph{local~t-spanner}\) of \(P\), is a sparse graph \(G\) over \(P\), such that, for any region \(\region \in \FF\), the subgraph restricted to \(\region\), denoted by \(\restrictY{G}{\region} = G_{P \cap \region}\), is a \(t\)-spanner for all the points of \(\region \cap P\). We present algorithms for the construction of local spanners with respect to several families of regions, such as homothets of a convex region. Unfortunately, the number of edges in the resulting graph depends logarithmically on the spread of the input point set. We prove that this dependency can not be removed, thus settling an open problem raised by Abam and Borouny. We also show improved constructions (with no dependency on the spread) of local spanners for fat triangles, and regular \(k\)-gons. In particular, this improves over the known construction for axis parallel squares. We also study a somewhat weaker notion of local spanner where one allows to shrink the region a "bit". Any spanner is a weak local spanner if the shrinking is proportional to the diameter. Surprisingly, we show a near linear size construction of a weak spanner for axis-parallel rectangles, where the shrinkage is \(\Emph{multiplicative}\).