Let S be a set of n points in IRd, and k an integer such that 1≤k≤n-2. Algorithms are given that construct fault-tolerant spanners for S. If in such a spanner at most k edges or vertices are removed, then each pair of points in the remaining graph is still connected by a short path. Our results include (i) an algorithm with running time O(n logd-1 n+kn log log n+k2n) that constructs a spanner with O(k2n) edges, that is resilient to k edge faults, (ii) an algorithm with running time O(n log n+k2n) that constructs a spanner with O(k2n) edges, that is resilient to k vertex faults, and (iii) an algorithm with running time O(n log n+ckn) that constructs a spanner of degree O(ck), whose total edge length is bounded by O(ck) times the weight of a minimum spanning tree of S, and that is resilient to k edge or vertex faults. Here, c is a constant that is independent of n and k.
