Spanner for the $0/1/\infty$ weighted region problem

Abstract

We consider the problem of computing an approximate weighted shortest path in a weighted subdivision, with weights assigned from the set $\{0,1,\infty \}$. We present a data structure $B$, which stores a set of convex, non-overlapping regions. These include zero-cost regions (0-regions) with a weight of $0$ and obstacles with a weight of $\infty$, all embedded in a plane with a weight of $1$. The data structure $B$ can be constructed in expected time $O(N+(n/{\epsilon }^3)(\log (n/\epsilon )+\log N))$, where $n$ is the total number of regions, $N$ represents the total complexity of the regions, and $1+\epsilon$ is the approximation factor, for any $0<\epsilon <1$. Using $B$, one can compute an approximate weighted shortest path from any point $s$ to any point $t$ in $O(N+n/{\epsilon }^3+(n/{\epsilon }^2)\log (n/\epsilon )+(\log N)/\epsilon )$ time. In the special case where the 0-regions and obstacles are polygons (not necessarily convex), $B$ contains a $(1+\epsilon )$-spanner of the input vertices.