Spanner for the 0/1/∞ weighted region problem

We consider the problem of computing an approximate weighted shortest path in a weighted subdivision, with weights assigned from the set \0, 1, ∞\. 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 ∞, all embedded in a plane with a weight of $1$. The data structure B can be constructed in expected time O(N + (n/ε³)(log(n/ε) + log N)), where n is the total number of regions, N represents the total complexity of the regions, and 1 + ε is the approximation factor, for any 0 < ε < 1. Using B, one can compute an approximate weighted shortest path from any point s to any point t in O(N + n/ε³ + (n/ε²) log(n/ε) + (log N)/ε) time. In the special case where the 0-regions and obstacles are polygons (not necessarily convex), B contains a (1 + ε)-spanner of the input vertices.