Optimal Spanners for Unit Ball Graphs in Doubling Metrics
share
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 𝒪(log^*n)-round distributed algorithm that given a unit ball graph G with n vertices and a positive constant ϵ < 1 finds a (1+ϵ)-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 𝒪(log^*n) rounds but has a 𝒪(logΔ) bound on its lightness, where Δ 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 𝒪(log^*n) rounds of communication. If a maximal independent set is known beforehand, our algorithms run in constant number of rounds.
READ FULL TEXT