Abstract
In this paper we devise an optimal construction of fault-tolerant spanners for doubling metrics. Specifically, for any -point doubling metric, any $\eps > 0$, and any integer , our construction provides a -fault-tolerant $(1+\eps)$-spanner with optimal degree within optimal time . We then strengthen this result to provide near-optimal (up to a factor of ) guarantees on the diameter and weight of our spanners, namely, diameter and weight , while preserving the optimal guarantees on the degree and the running time . Our result settles several fundamental open questions in this area, culminating a long line of research that started with the STOC'95 paper of Arya et al.\ and the STOC'98 paper of Levcopoulos et al. On the way to this result we develop a new technique for constructing spanners in doubling metrics. Our spanner construction is based on a novel \emph{hierarchical cover} of the metric, whereas most previous constructions of spanners for doubling and Euclidean metrics (such as the net-tree spanner) are based on \emph{hierarchical partitions} of the metric. We demonstrate the power of hierarchical covers in the context of geometric spanners by improving the state-of-the-art results in this area.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.