From hierarchical partitions to hierarchical covers

A (1+ε)-spanner for a doubling metric (X, δ) is a subgraph H of the complete graph corresponding to (X, δ), which preserves all pairwise distances to within a factor of 1 + ε. A natural requirement from a spanner, which is essential for many applications (mainly in distributed systems or wireless networks), is to be robust against vertex and edge failures -- so that even when some vertices and edges in the network fail, we still have a (1 + ε)-spanner for what remains. The spanner H is called a k-fault-tolerant (1 + ε)-spanner, for 1 ≤ k ≤ n -- 2, if for any F ⊆ X with |F| ≤ k, the graph H -- F (obtained by removing from H the vertices of F and their incident edges) is a (1 + ε)-spanner for X -- F.