Optimal Spanners for Unit Ball Graphs in Doubling Metrics

Resolving an open question from 2006, we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple $\mathcal{O}(\log^*n)$-round distributed algorithm that given a unit ball graph $G$ with $n$ vertices and a positive constant $\epsilon < 1$ finds a $(1+\epsilon)$-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the algorithm of Damian, Pandit, and Pemmaraju which runs in $\mathcal{O}(\log^*n)$ rounds but has a $\mathcal{O}(\log \Delta)$ bound on its lightness, where $\Delta$ is the ratio of the length of the longest edge in $G$ to the length of the shortest edge. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersection per node. This is the first distributed low-intersection topology control algorithm to the best of our knowledge. Our distributed algorithms rely on the maximal independent set algorithm of Schneider and Wattenhofer that runs in $\mathcal{O}(\log^*n)$ rounds of communication. If a maximal independent set is known beforehand, our algorithms run in constant number of rounds.