English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we devise an optimal construction of fault-tolerant spannersfor doubling metrics. Specifically, for any $n$-point doubling metric, any$\eps > 0$, and any integer $0 \le k \le n-2$, our construction provides a$k$-fault-tolerant $(1+\eps)$-spanner with optimal degree $O(k)$ within optimaltime $O(n \log n + k n)$.  We then strengthen this result to provide near-optimal (up to a factor of$\log k$) guarantees on the diameter and weight of our spanners, namely,diameter $O(\log n)$ and weight $O(k^2 + k \log n) \cdot \omega(MST)$, whilepreserving the optimal guarantees on the degree $O(k)$ and the running time$O(n \log n + k n)$.  Our result settles several fundamental open questions in this area,culminating a long line of research that started with the STOC'95 paper of Aryaet al.\ and the STOC'98 paper of Levcopoulos et al.  On the way to this result we develop a new technique for constructingspanners in doubling metrics. Our spanner construction is based on a novel\emph{hierarchical cover} of the metric, whereas most previous constructions ofspanners for doubling and Euclidean metrics (such as the net-tree spanner) arebased on \emph{hierarchical partitions} of the metric. We demonstrate the powerof hierarchical covers in the context of geometric spanners by improving thestate-of-the-art results in this area.

From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics