Given a set S of n points, a weight function w to associate a non-negative weight to each point in S, a positive integer k ≥ 1, and a real number ∈ ＞ 0, we devise the following algorithms to compute a k-vertex fault-tolerant spanner network G(S,E) for the metric space induced by the weighted points in S: (1) When the points in S are located in a simple polygon, we present an algorithm to compute G with multiplicative stretch 10~(1/2) + ∈, and the number of edges in G is O(kn(lg n)~2). (2) When the points in S are located in the free space of a polygonal domain P, we present an algorithm to compute G of size O(h~(1/2)kn(lg n)~2) and its multiplicative stretch is 6 + ∈. Here, h is the number of simple polygonal holes in P.
展开▼
