Fault-Tolerant Additive Weighted Geometric Spanners
share
Let S be a set of n points and let w be a function that assigns non-negative weights to points in S. The additive weighted distance d_w(p, q) between two points p,q belonging to S is defined as w(p) + d(p, q) + w(q) if p q and it is zero if p = q. Here, d(p, q) denotes the (geodesic) Euclidean distance between p and q. A graph G(S, E) is called a t-spanner for the additive weighted set S of points if for any two points p and q in S the distance between p and q in graph G is at most t.d_w(p, q) for a real number t > 1. Here, d_w(p,q) is the additive weighted distance between p and q. For some integer k ≥ 1, a t-spanner G for the set S is a (k, t)-vertex fault-tolerant additive weighted spanner, denoted with (k, t)-VFTAWS, if for any set S' ⊂ S with cardinality at most k, the graph G S' is a t-spanner for the points in S S'. For any given real number ϵ > 0, we obtain the following results: - When the points in S belong to Euclidean space R^d, an algorithm to compute a (k,(2 + ϵ))-VFTAWS with O(kn) edges for the metric space (S, d_w). Here, for any two points p, q ∈ S, d(p, q) is the Euclidean distance between p and q in R^d. - When the points in S belong to a simple polygon P, for the metric space (S, d_w), one algorithm to compute a geodesic (k, (2 + ϵ))-VFTAWS with O(k n/ϵ^2n) edges and another algorithm to compute a geodesic (k, (√(10) + ϵ))-VFTAWS with O(kn(n)^2) edges. Here, for any two points p, q ∈ S, d(p, q) is the geodesic Euclidean distance along the shortest path between p and q in P. - When the points in S lie on a terrain T, an algorithm to compute a geodesic (k, (2 + ϵ))-VFTAWS with O(k n/ϵ^2n) edges.
READ FULL TEXT