Spanner for the $\mathrm{𝟎}\mathbf{/}\mathrm{𝟏}\mathbf{/}\mathbf{\infty }$ Weighted Region Problem

Our work is closely related to the data structure and algorithm by Gewali et al. [15] to solve the $0/1/\mathrm{\infty }$ weighted region problem. Their algorithm takes a polygonal domain with $N$ vertices as input and constructs a critical graph ${𝒢}^{\ast }=({𝒱}^{\ast },{ℰ}^{\ast })$ (a type of visibility graph) with $O(N^2)$ edges. Dijkstra’s shortest path algorithm can be used on ${𝒢}^{\ast }$ to compute a weighted shortest path between any pair of vertices in $O(N^2)$ time.

In $0/1/\mathrm{\infty }$ weighted regions, a weighted shortest path $P^{\ast }$ avoids obstacles and traverses the 0-regions freely, while minimizing its length in the plane ($1$-region). Consider two (closed) regions $A$ and $B$, each either a 0-region or an obstacle. The key observation in [15] is that an edge in $P^{\ast }$ connecting $A$ and $B$ must be locally optimal (see Fact 16). For example, an edge $(a,b)$ connecting two convex 0-regions $A$ and $B$ must be perpendicular to the tangent touching $a\in A$ and the tangent touching $b\in B$. Gewali et al. [15] showed that $G^{\ast }$ contains all such locally optimal edges in $G^{\ast }$, which implies that $G^{\ast }$ must contain the optimal path between any pair of vertices in $G^{\ast }$.

In this paper, we build on the work by Gewali et al. [15] with a focus on the $0$-regions as they are not handled well by existing approximation schemes (using sample points or tessellation). In Section 2, we consider the $0/1$ weighted region problem where the 0-regions are convex but not necessarily polygonal.

The high-level idea is that, in order to obtain $(1+\epsilon )$-approximate shortest paths, we place $O(1/\epsilon )$ sample points on the boundary of each $0$-region; the number of sample points is independent of other parameters. Using these sample points, we construct a $\mathrm{\Theta }$-graph and $O(1/\epsilon )$ trapezoidal maps, which are part of our data structure $ℬ$. The trapezoidal maps ensure the existence of good paths between $0$-regions that are close²²2A precise definition is provided in Lemma 8 and 10, Section 2. to each other, while the $\mathrm{\Theta }$-graph ensures the same for $0$-regions that are far from each other. To the best of our knowledge, our algorithm is the first near-linear time $(1+\epsilon )$-approximation algorithm that finds an approximated weighted shortest path in a $0/1$ weighted region. Note that both Theorem 1 and 3 apply to polygonal domains with non-convex regions, since they can be triangulated into a linear number of triangles.

To use our algorithm on an application, we prove the above theorem in a more general setting, where the 0-regions are non-polygonal. In Section 3, we use our algorithm to approximate the partial weak Fréchet similarity of two polygonal curves. This problem was first studied by Buchin et al. [7], and they presented a cubic time algorithm. De Carufel et al. [13] later transformed the problem into a weighted shortest path problem amidst $0/1$-regions. Using Theorem 1, our algorithm is the first near-quadratic time $(\sqrt{2}+\epsilon )$-approximation algorithm for computing the partial weak Fréchet similarity between a pair of polygonal curves.

Buchin et al. [8] showed that there is no strongly subquadratic time algorithm for approximating the weak Fréchet distance within a factor less than 3 unless the strong exponential-time hypothesis fails. Approximating the partial weak Fréchet similarity is at least as hard as approximating the weak Fréchet distance. As a result, it is unlikely that a subquadratic time algorithm exists.

In Section 4, we generalise our data structure to also allow convex obstacles that cannot be traversed, i.e., obstacles of weight $\mathrm{\infty }$. Let $\text{d}(\mathrm{a},\mathrm{b})$ denote the weight of the weighted shortest path from $a$ to $b$ amidst $0/1/\mathrm{\infty }$-weighted region. By introducing additional sample points, we show that if we need to take a detour from a sample point $a$ to a sample point $b$, there exists a set $D$ (a detour) of edges in $ℬ$ such that the total length of $D$ approximates the distance $\text{d}(\mathrm{a},\mathrm{b})$ within a factor of $1+\epsilon$.

In the special case that the 0-regions and obstacles are polygonal, $ℬ$ is a $(1+\epsilon )$-spanner of the input vertices. To the best of our knowledge, our algorithm is the first near-linear time $(1+\epsilon )$-approximation algorithm for the weighted shortest path in a $0/1/\mathrm{\infty }$ weighted region.

In order to define our data structure, we first define a set of directions. Let be a fixed positive real number. Let $r(k\theta )$ be the direction with a counter-clockwise angle of $k\theta$ with the positive $x$-axis. Let $r(p,k\theta )$ be the ray originating from the point $p$ with a counter-clockwise angle of $k\theta$ with the positive $x$-axis. To simplify the discussion, we will assume that $(\pi /2)/\theta \in \mathbb{Z}$ to guarantee that if $r(k\theta )$ exists, then so does $r(k\theta +\pi /2)$.

For a 0-region $A$, we define a set $𝒮𝒫(A)$ of sample points on the boundary of $A$. Let $sp(A,k\theta )$ be a sample point on the boundary $\partial A$ of $A$ such that $sp(A,k\theta )$ is extreme in the direction $r(k\theta )$ (see Figure 1). When the geometric region $A$ is clear from context, we write $sp(k\theta )$ instead of $sp(A,k\theta )$.

Let $\partial A(a,a^{\prime })$ define the subset of $\partial A$ traversed from point $a$ to point $a^{\prime }$ in counter-clockwise order, where $a,a^{\prime }\in \partial A$. We say a line $l$ overlaps $A$ if $l$ and $A$ intersect at more than one point. We say two regions, $A$ and $B$, are non-overlapping if their interiors do not intersect.

A point $p\in \partial A$ can be an extreme point for more than one direction, in which case we call $p$ a vertex of $A$. There may be more than one extreme point on $A$ for a single direction. If $p$ is the extreme point on $A$ for consecutive directions $\{r(k\theta ),r((k+1)\theta ),\mathrm{\dots },r((k+m)\theta )\}$, we say $p=sp(k\theta )$, $p=sp((k+1)\theta )$, …, and $p=sp((k+m)\theta )$ simultaneously. If there is more than one extreme point for a single direction $r(k\theta )$, these extreme points must lie on some segment $ab\subseteq \partial A$, and we say both $a$ and $b$ are $sp(k\theta )$. The sample points on the boundary of a convex region can be computed by traversing the boundary.

Using the sample points on a 0-region $A$, we can generate a simplified $0$-region (a convex polygon) $\mathrm{𝚜𝚒𝚖𝚙𝚕}(A)$ by connecting adjacent sample points of every 0-region (see Figure 1). Using the set $\mathrm{𝚜𝚒𝚖𝚙𝚕}(𝒵)$ of simplified 0-regions, we will generate a set of trapezoidal maps, and we say $\mathrm{𝚜𝚒𝚖𝚙𝚕}(A)$ and $\mathrm{𝚜𝚒𝚖𝚙𝚕}(B)$ are adjacent if they are both adjacent to the same face in a trapezoidal map. We construct the query data structure $ℬ$ using Algorithm 1. We analyse $ℬ$ in the full version. Let $\parallel AB\parallel$ denote the Euclidean distance between two geometric objects $A$ and $B$.

Before arguing that there exists a good path using the edges constructed, we start with an observation about the pair of points realising the shortest distance between two 0-regions. For a convex region $A$ and a point $p\in \partial A$, there exists at least one supporting line $l=l_t(A,p)$ going through $p$ such that $A$ lies entirely in one of the two halfplanes determined by $l$ [19]. Let $p\in \partial A$, and $q\in \partial B$. We can observe that if $pq$ realises $\parallel AB\parallel$, then $pq$ must be perpendicular to a pair of supporting lines $l_t(A,p)$ and $l_t(B,q)$.

We will show that if $pq$ realises the distance between two 0-regions, we can transform $pq$ into another segment $p{q}^{\prime }$ such that $p{q}^{\prime }$ is parallel to some direction $r(k\theta )$, and $\parallel p{q}^{\prime }\parallel$ approximates $\parallel pq\parallel$. To do this, we first need a fact (see the full version for a proof).

Let $pq$ realise $\parallel AB\parallel$. We consider the scenario when $\parallel pq\parallel$ is relatively small compared to the horizontal span of (say) $B$. Using the above lemma, we will show that we have constructed a set of edges in $ℰ$ connecting two sample points $a\in A$ and $b\in B$, such that the total weight of these edges approximates $\parallel pq\parallel$.

In Step 4 of Algorithm 1, we constructed a $\mathrm{\Theta }$-graph ${𝒢}_{\mathrm{\Theta }}=({𝒱}_{\mathrm{\Theta }},{ℰ}_{\mathrm{\Theta }})$ using the defined sample points. The vertices ${𝒱}_{\mathrm{\Theta }}$ are simply all sample points. The edges in ${ℰ}_{\mathrm{\Theta }}$ are constructed using the standard $\mathrm{\Theta }$-graph construction [11]. Recall that in Algorithm 1, for every edge $(p,q)\in {ℰ}_{\mathrm{\Theta }}$, with $p\in A$, $q\in B$, and $A\ne B$, we add an edge $(p,q)$ to $ℰ$, and set $\text{w}(\mathrm{p},\mathrm{q})=\parallel \mathrm{pq}\parallel$.

The $\mathrm{\Theta }$-graph constructs a set of “good” edges in $ℰ$ when the distances between $p$ (resp. $q$) and its adjacent sample points are small compared to $\parallel pq\parallel$. In this case, we argue that there exists a pair of sample points $a\in A$ and $b\in B$, such that $\parallel ab\parallel \le (1/\cos (\theta ))\cdot \parallel pq\parallel$. Similar to Lemma 7, we prove the following geometric property in the full version.

In the case that both $p$ and $q$ are close to their adjacent sample points, we prove that there exists a pair $(a,b)$ of sample points such that $\parallel ab\parallel$ approximates $\parallel pq\parallel$ in the full version.

For now, assume that $s$ and $t$ lie in some 0-region. An optimal $s$-$t$ path $P^{\ast }$ consists of a set of segments, where the endpoints of each segment lie on the boundaries of the 0-regions. A segment $pq$ either lies within a 0-region or connects two different 0-region. Since it costs nothing to follow an edge inside a 0-region, the weight of $P$ is the total weight of those edges connecting different 0-regions.

Let $pq$ realise the distance between 0-regions $A$ and $B$, where $p$ lies on $\partial A$ between sample points $a$ and $a^{\prime }$, and $q$ lies on $\partial B$ between sample points $b$ and $b^{\prime }$. In Lemma 8, we have shown that if $\max \{\parallel p{a}^{\prime }\parallel ,\parallel qb\parallel \}\ge (\sin (\alpha )/\cos (\theta ))\cdot \parallel pq\parallel$ or $\max \{\parallel pa\parallel ,\parallel q{b}^{\prime }\parallel \}\ge (\sin (\beta )/\cos (\theta ))\cdot \parallel pq\parallel$, there exists a path $P\subseteq ℰ$ from a sample point on $A$ to a sample point on $B$ of length at most $(\cos (\beta )/\cos (\theta ))\cdot \parallel pq\parallel$.

In Lemma 10, we have shown that if and , there exist sample points $a\in A$ and $b\in B$, such that . To obtain a path between $a$ and $b$ in this case, we rely on the $\mathrm{\Theta }$-graph. The tightest bounds on the length of this path are due to Bose et al. [4], who showed that the spanning ratio of a $\mathrm{\Theta }$-graph is at most $r_{\theta }=1+2\sin (\theta /2)/(\cos (\theta /2)-\sin (\theta /2))$. Our final approximation ratio is $(1/\cos (\theta ))\cdot r_{\theta }$. Given an input approximation factor $1+\epsilon$, we can compute a desired angle $\theta \in O(\epsilon )$. The undirected graph $𝒢\in ℬ$ is therefore a $(1+\epsilon )$-spanner of the sample points. See the full version for details.

Given a pair of query points $s$ and $t$, we add $s$ and $t$ to $ℬ$. We treat both $s$ and $t$ as 0-regions with no interior to enable previous lemmas, yielding the theorem below. See the full version for details.

In order to deal with obstacles, we need to define two new types of sample points. For clarity, we refer to the sample points defined previously as the original sample points. In Section 2, a trapezoidal map $ℳ(k)$ was only used to determine if two 0-regions should be connected, and we did not explicitly compute the intersection of a vertical segment and the boundary of a region. With the introduction of obstacles, we do need such intersections. Consider a sample point $a$. When constructing $ℳ(k)$, we shoot two vertical rays from $a\in A$, one upwards and one downwards. Let $p$ be the first intersection of $r(a,k)$ with the boundary of some region that is not $A$. We call $p$ a propagated sample point.

The other type of sample points we need is the tangent sample points. Given two disjoint obstacles $A$ and $B$, and a common tangent $l$, if $l$ touches $A$ at point $a$ and $B$ at $b$, we add $a$ and $b$ as tangent sample points. When we say a point $a$ is a sample point, $a$ can be any type of sample point.

Recall that $\mathrm{𝚜𝚒𝚖𝚙𝚕}(A)$ is the simplified region by connecting every pair of adjacent sample points of $A$. $\mathrm{𝚜𝚒𝚖𝚙𝚕}(𝒵)$ is the set of simplified 0-regions, and $\mathrm{𝚜𝚒𝚖𝚙𝚕}(𝒪)$ is the set of simplified obstacles. We formally define the construction of our data structure. Given a set $𝒪$ of convex obstacles and a set $𝒵$ of convex $0$-regions, we build our data structure using Algorithm 2. See the full version for the analysis.

The structure of the rest of the section is as follows. By Lemma 14, the distance between two adjacent sample points on the boundary of an obstacle approximates the straight line segment. Therefore, we show that we can “snap” the vertices of an optimal path to our sample points. For every segment $pq\subseteq P^{\ast }$, we then argue that either the trapezoidal map or the $\mathrm{\Theta }$-graph contains a path approximating $\parallel pq\parallel$ to within a factor of $1+\epsilon$.

We first argue that if $a$ and $a^{\prime }$ are adjacent sample points of $A$, then $\parallel a{a}^{\prime }\parallel$ approximates $\parallel \partial A(a,a^{\prime })\parallel$ within a factor of $\sec (\theta /2)$. Therefore, if we find a path $P$ amidst the simplified obstacles, we only need to pay a small factor to transform $P$ into a path amidst the original obstacles. Then, we prove that if $pq$ is part of the optimal path, we can replace $pq$ with a path $P\subseteq ℰ$, such that $\text{w}(\mathrm{P})$ approximates $\parallel pq\parallel$. See the full version for a formal proof.

The above lemma implies the following. Let ${\text{d}}_{\text{S}}(\mathrm{a},\mathrm{b})$ be the distance between point $a$ and point $b$ amidst simplified obstacles and simplified 0-regions, and let $P$ be the path achieving this distance. If we partition $P$ using the sample points, in the worst case, each segment connects adjacent sample points on obstacles. This implies the following corollary.

Gewali et al. [15] defined three types of locally optimal edges joining two simple polygonal regions, and they proved that the shortest path from $s$ to $t$ must be comprised of these locally optimal edges [15, Lemma 2.5] (ignoring edges in 0-regions). For convex obstacles and 0-regions, we need to consider only four types of segments.

In Section 4.3.1, 4.3.2, and 4.3.3, we handle each type of edge in Case 1, 2, and 3, respectively. For an edge $pq$ in each of these cases, we argue that there exists a good path in $𝒢\in ℬ$ that approximates $pq$. Section 4.4 summarises the approximation ratio using the Case 4 edges. In the following lemmas, we assume without loss of generality that $pq$ lies between the direction $r(k\theta )$ and $r((k+1)\theta )$, and $\alpha$ (resp. $\beta$) is the measure of the acute angle between $r(p,k\theta )$ (resp. $r(p,(k+1)\theta )$) and $pq$. By Corollary 15, we consider only simplified obstacles. We delegate the full proofs to the appendix.

In Lemma 19, 20, and 21, we have shown that for every segment $pq$ in Case 1-3 in Fact 16, either there exists a path $P\subseteq ℰ$ such that $\text{w}(\mathrm{P})$ approximates $\parallel pq\parallel$, or there exist two sample points $a$ and $b$ such that ${\text{d}}_{\text{S}}(\mathrm{p},\mathrm{a})+{\text{d}}_{\text{S}}(\mathrm{a},\mathrm{b})+{\text{d}}_{\text{S}}(\mathrm{b},\mathrm{q})$ approximates $\parallel pq\parallel$. Taking the maximum ratio in the three lemmas, we have the following.