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 ge 1$, and a real number $epsilon > 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 $sqrt{10}+epsilon$, and the number of edges in $G$ (size of $G$) is $O(k n (lg{n})^2)$. (2) When the points in $S$ are located in the free space of a polygonal domain $cal P$ with $h$ number of obstacles, we present an algorithm to compute $G$ with multiplicative stretch $6+epsilon$ and size $O(sqrt{h} k n(lg{n})^2)$. (3) When the points in $S$ are located on a polyhedral terrain, we devise an algorithm to compute $G$ with multiplicative stretch $6+epsilon$ and size $O(k n (lg{n})^2)$.
تحميل البحث