Vertex Fault-Tolerant Spanners for Weighted Points in Polygonal Domains

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 $ϵ>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}+ϵ$, and the number of edges in $G$ (size of $G$) is $O(kn(\lg n{)}^2)$. (2) When the points in $S$ are located in the free space of a polygonal domain $\mathcal{P}$ with $h$ number of obstacles, we present an algorithm to compute $G$ with multiplicative stretch $6+ϵ$ and size $O(\sqrt{h}kn(\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+ϵ$ and size $O(kn(\lg n{)}^2)$.