Fréchet Distance in Unweighted Planar Graphs

Several conditional lower bounds exist for computing the Fréchet distance or its constant-factor approximations. These results rely on complexity assumptions such as the Orthogonal Vector Hypothesis (OVH) and the Strong Exponential Time Hypothesis (SETH) [32]. Bringmann [7] established that no algorithm can compute the (discrete or continuous) Fréchet distance between two polygonal curves of $n$ vertices in $O(n^{2-\delta })$ time for any $\delta >0$, unless OVH fails. The same lower bound holds for small constant-factor approximations. Bringmann’s proof originally involved self-intersecting curves in the plane, but later work by Bringmann and Mulzer [9] extended the result to intersecting curves in ${ℝ}^1$. Buchin, Ophelders, and Speckmann [12] further demonstrated that the same lower bound applies for any better-than-3-approximation algorithm for pairwise disjoint planar curves in ${ℝ}^2$, or intersecting curves in ${ℝ}^1$.

Bringmann’s lower bound [7] holds also for unbalanced inputs: given two curves with $n$ and $m$ vertices in the plane, no algorithm can compute the Fréchet distance in $O({(nm)}^{1-\delta })$ time assuming OVH. Driemel, van der Hoog and Rotenberg [19] give a similar lower bound for paths in a weighted planar graph. They prove that, unless OVH fails, no $O({(nm)}^{1-\delta })$-time algorithm can $1.01$-approximate the discrete Fréchet distance between arbitrary paths in a weighted planar graph – even if the ratio between smallest and highest weight is bounded by a constant. This lower bound applies only to weighted graphs and does therefore not exclude the existence of a fast algorithm on unweighted planar graphs. A closer inspection of their argument reveals that their proof cannot simply be adapted to the unweighted case by subdividing long edges often enough. In this case, new vertices get introduced to the graph and their arguments break down.

These lower bounds can be circumvented if the input is well-behaved. Driemel, Har-peled and Wenk [17] consider three classes of curves in ${ℝ}^d$ which are well-behaved as long as their corresponding behavioural parameter is low. These are $c$-packed curves [17, 8], $\varphi$-low density curves [17], and $\kappa$-bounded curves [3, 4, 17]. They show algorithms to compute a $(1+\epsilon )$-approximation between two well-behaved curves whose running time is near-linear in $n$ and $m$. Gudmundsson, Mirzanezhad, Mohades, and Wenk consider the special case where all edges of the input curves are long with respect to their Fréchet distance [23]. In this case, the Fréchet distance can be computed in $O((n+m)\log (n+m))$ time [23]. Driemel, van der Hoog, and Rotenberg [19] show that if the input are walks in a graph $G$ and one of the walks is restricted to a $c$-packed or $\kappa$-straight path, then there exists $(1+\epsilon )$-approximations that take near-linear time.

Driemel, van der Hoog, and Rotenberg [19] ruled out a strongly subquadratic algorithm for a $1.01$-approximation between paths in a weighted graph, while the construction by Buchin, Ophelders, and Speckmann [12] rules out a strongly subquadratic algorithm for a $3$-approximation between walks in an unweighted planar graph. We consider the discrete Fréchet distance between paths in an unweighted planar graph. We prove (Theorem 5) that no strongly-subquadratic $1.25$-approximation algorithm exists unless OVH fails, thereby improving both the generality (and also the approximation factor for planar graphs).

Next, we prove that adding graph structure circumvents this lower bound. If $G$ is an unweighted regular tiling of the plane, then there exists an $\tilde{O}({(n+m)}^{1.5})$-time algorithm to compute the Fréchet distance ${\mathrm{D}}_{\mathrm{G}}(P,Q)$, between curves of length $n$ and $m$. Our results have natural implications in the plane, for a special class of well-behaved curves ($(\epsilon ,\delta )$-curves, to be defined). For those, we can compute the Fréchet distance under the $L_1$ metric (respectively, approximate it for any $L_c$ metric) in $\tilde{O}(\frac{\sqrt{\delta }}{\epsilon }{(n+m)}^{1.5})$ time (respectively, $\tilde{O}(\frac{\delta }{{\epsilon }^2}{(n+m)}^{1.5})$ time). For completeness, we explain the continuous analogy to $(\epsilon ,\delta )$-curves in the full version of this paper. We also compare this new curve class to existing well-behaved curve classes in the full version.

We focus on the decision variant where the input includes some $\mathrm{\Delta }\ge 0$ and the goal is to output whether ${\mathrm{D}}_{\mathrm{G}}(P,Q)\le \mathrm{\Delta }$. The $\mathrm{\Delta }$-free space matrix $M_{\mathrm{\Delta }}$ is the $n$ by $m$ matrix where $M_{\mathrm{\Delta }}[i,j]$ is $0$ if $\mathrm{dist}(p_i,q_j)\le \mathrm{\Delta }$ and $1$ otherwise. We follow geometric convention, where $i$ denotes the column of $M_{\mathrm{\Delta }}$ (column $i$ corresponds to some $p_i\in P$. Column entries with value $0$ correspond to $q_j\in Q$ with $\mathrm{dist}(p_i,q_j)\le \mathrm{\Delta }$). Eiter and Mannila [20] define a directed graph over $M_{\mathrm{\Delta }}$ where there is an edge from $M_{\mathrm{\Delta }}[a,b]$ to $M_{\mathrm{\Delta }}[c,d]$ if and only if $c\in \{a,a+1\}$, $d\in \{b,b+1\}$ and $M_{\mathrm{\Delta }}[a,b]=M_{\mathrm{\Delta }}[c,d]=0$. They prove that ${\mathrm{D}}_{\mathrm{G}}(P,Q)\le \mathrm{\Delta }$ if and only if there exists a directed path from $(1,1)$ to $(n,m)$ in this graph.

Our conditional lower bound reduces from the Orthogonal Vector Hypothesis. The input consists of two ordered sets of $d$-dimensional Boolean vectors $U,W$ of sizes $|U|=n$ and $|W|=m$. We denote for $u\in U$ by $u_i\in \{0,1\}$ its $i$’th component. The OV problem is to find out if some vector of $U$ is orthogonal to some vector of $W$.

We consider each vector in $U$ (or $W$) as a string of $d$ bits. We denote by $\mathrm{str}(U)$ and $\mathrm{str}(W)$ the concatenation of all strings in $U$ and $W$, respectively. A substring of some string $s_1{s}_2\mathrm{\dots }{s}_k$ is the sequence $s_a{s}_{a+1}\mathrm{\dots }{s}_{b-1}{s}_b$ for some $1\le a\le b\le k$.

A regular tiling $T$ is an infinite plane graph where each face is a regular polygon and each face has the same degree. There exist exactly three regular tilings [22]: the triangular, square, and hexagonal tiling (Figure 1). Without loss of generality, we assume that our tilings are axis-aligned. A face $F$ of $T$ is an open region bounded by the edges of $T$, we denote by $\overline{F}$ its closure. The edge length of $T$ is the length of any edge. A tiling is unit if its edges have unit length. A path in $T$ is a path in its corresponding graph. We always denote by $T$ a unit tiling where $(0,0)$ is a vertex of $T$. For any pair of vertices $p,q$ of $T$, the term $\mathrm{dist}(p,q)$ denotes the distance in the graph $T$. We assume that we can compute $\mathrm{dist}(p,q)$ in constant time. Our algorithm considers what we will call a super-tiling of $T$ and a natural partition of the edges of $P$ and $Q$ into subpaths.

Given a path $P$ in a tiling $T$ and a super-tiling $𝕋$ of $T$, we want to consider how $𝕋$ splits $P$ into smaller snippets, each snippet “belonging” to a face of $𝕋$. More formally:

We show a subquadratic algorithm to decide whether ${\mathrm{D}}_{\mathrm{T}}(P,Q)\le \mathrm{\Delta }$ if $P$ and $Q$ are paths in a tiling $T$. We compute a monotone walk from $(1,1)$ to $(n,m)$ in $M_{\mathrm{\Delta }}$ by efficiently propagating reachability information across submatrices of $M_{\mathrm{\Delta }}$. For integers $i,i^{\prime }\in [n]$ and $j,j^{\prime }\in [m]$ with $i\le i^{\prime }$ and $j\le j^{\prime }$ we denote by $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$ the submatrix of $M_{\mathrm{\Delta }}$ that consist of all entries $M_{\mathrm{\Delta }}[x,y]$ for $(x,y)\in [i,i^{\prime }]\times [j,j^{\prime }]$. We define the bottom-left facets of $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$ as all entries $\{M_{\mathrm{\Delta }}[i,y]\mid y\in [j,j^{\prime }]\}$ and $\{M_{\mathrm{\Delta }}[x,j]\mid x\in [i,i^{\prime }]\}$. The top-right facets are defined as the entries $\{M_{\mathrm{\Delta }}[i^{\prime },y]\mid y\in [j,j^{\prime }]\}$ and $\{M_{\mathrm{\Delta }}[x,j^{\prime }]\mid x\in [i,i^{\prime }]\}$.

Finally, we introduce a new class of well-behaved curves in the plane. Intuitively, an $(\epsilon ,\delta )$-curve, for small $\delta$, is a curve composed of short edges that does not revisit the same region of the plane too frequently. Formally, fix a universal constant $\gamma \in O(1)$. Let $P$ be a curve in the plane, and let $B_{\epsilon }$ denote the set of all balls (in Euclidean metric) of radius $\epsilon$ centred at the vertices of $P$. We say that $P$ is an $(\epsilon ,\delta )$-curve if all its edges have length at most $\gamma$, and any point in the plane lies in at most $\delta$ balls from $B_{\epsilon }$.

For any given pair $(P,\epsilon )$, $\delta$ is determined. As $\epsilon$ decreases, so may $\delta$. If $\delta$ remains large for small $\epsilon$, then many vertices of $P$ are densely clustered – i.e., effectively, the curve frequently revisits the same locations. We present an exact algorithm for the Discrete Fréchet distance under the $L_1$ metric with a linear dependency on $\frac{\sqrt{\delta }}{\epsilon }$. We assume that the input specifies a desirable value of $\epsilon$, and that this yields a favourable corresponding $\delta$. Imposing that $\delta$ is constant amounts to requiring that the curve does not revisit any $\epsilon$-ball more than a constant number of times – a restriction that somewhat resembles the well-studied $c$-packed curves [17, 19, 8]. In the full version of this paper, we discuss in detail how our new class relates to the prior well-behaved curve classes.

To prove Theorem 6, we first introduce a few new concepts. Let $T$ be a regular, unit, axis-aligned tiling. Based on $T$, we construct a super-tiling $𝕋$ of the same type as $T$, that is, if $T$ is a square/triangular/hexagonal tiling, then $𝕋$ is also a square/triangular/hexagonal tiling. We state our results in general terms, but for ease of reading, the reader may assume $T$ is a square tiling. For a (super) tiling $𝕋$, we define the halfslabs of any face $F$ of $𝕋$ by picture (Figure 4).

Having faces $F,F^{\prime }$ be well-separated proves to be very useful, since in such a pair the distance between some vertex $p\in V(T)\cap \overline{F}$ and $q\in V(T)\cap \overline{F^{\prime }}$ can be well-understood. We provide an efficient algorithm to compute the pairwise Fréchet distance between subpaths of $P$ and $Q$ whenever their corresponding faces in $𝕋$ are well-separated. We identify a sufficient condition that ensures that some pair $F,F^{\prime }$ is well-separated, based on the alignment of the two:

Consider first the case where $T$ is a square tiling (and so $𝕋$ is too). The situation is depicted in Figure 5 (a). If the faces $F,F^{\prime }$ are not aligned, then $F^{\prime }$ is contained in one of the four regions $(R_1,R_2,R_3,R_4)$ of the plane formed by the halfslabs of $F$. Let $v$ be the vertex at the apex of the region which contains $F^{\prime }$. We claim that for any vertices $p\in V(T)\cap \overline{F}$ and $q\in V(T)\cap \overline{F^{\prime }}$, there exists a shortest path between $p$ and $q$ that passes through $v$. Hence $F$ and $F^{\prime }$ are well-separated. The claim is easy to see from the properties of shortest paths in grid graphs. We provide an alternative proof of the claim, with the advantage that it can be more easily generalized to the triangular and hexagonal grid. See Figure 5 (b) and consider for $i=1,2,\mathrm{\dots }$ the circles of radius $i$ in the plane graph $T$ centred around $p$, and $q$.

We can see that $h_i,h_i^{\prime }$ can be described as diamonds with four sides. Let us among the four sides of $h_i$ denote by $X_i$ the side that is facing towards $F^{\prime }$. Likewise, let us among the four sides of $h_i^{\prime }$ denote by $X_i^{\prime }$ the side that is facing towards $F$. Note that all of $X_i,X_i^{\prime }$ are parallel for $i\in \mathbb{N}$. Let $\mathrm{\ell }$ denote the line through vertex $v$ parallel to the $X_i$. Let $a\in \mathbb{N}$ be minimal such that $h_a$ touches $\mathrm{\ell }$. Since $X_a$ is parallel to $\mathrm{\ell }$, we have $X_a\subseteq \mathrm{\ell }$. Furthermore, no matter which $p\in V(T)\cap \overline{F}$ was chosen as the centre of the circles $h_i$, we always have $v\in X_a$. This follows due to the way and the angle in which the circles $h_i$ expand. Analogously, let $b\in \mathbb{N}$ be minimal such that $h_b^{\prime }$ touches $\mathrm{\ell }$. Due to the way the $h_i^{\prime }$ expand and since $F$ and $F^{\prime }$ are not aligned, we have $v\in X_b^{\prime }$. Now, the circle $h_a$ is entirely on one side of $\mathrm{\ell }$, the circle $h_b^{\prime }$ is entirely on the other side, and $v\in h_a\cap h_b^{\prime }$. By definition of $h_a,h_b^{\prime }$, this implies $\mathrm{dist}(p,q)=a+b$ and there is a shortest path between $p,q$ that passes through $v$.

For the case of triangular and hexagonal grids, the situation is depicted in Figures 6 and 7. Here the halfslabs divide the plane into 6 cone-shaped regions $R_1,\mathrm{\dots },R_6$. Let $v_j$ be the point at the apex of $R_j$ for $j=1,\mathrm{\dots },6$. Note that $v_j$ is also a vertex of $V(T)$. For both the triangular and hexagonal grid, the definitions of $h_i,h_i^{\prime },X_i,X_i^{\prime },\mathrm{\ell },a,b$ can be made in an analogous matter. Analogously, it follows that $v_j\in h_a\cap h_b^{\prime }$ which concludes the lemma. $◀$

Given $T$ and paths $P$ and $Q$, we first compute a suitable super-tiling:

Our proof is inspired by that of Chan and Rahmati [14, Lemma 1], who prove an analogous statement for grids and curves in higher-dimensional real space (without graphs). For the proof, we assume without loss of generality that $T$ is axis-aligned.

Let $f=\lceil \sqrt{n+m}\rceil$, and let ${𝕋}_0$ be any axis-aligned super-tiling of $T$ with an edge length in $\mathrm{\Theta }(f)$. For each $i\in [f-1]$, define ${𝕋}_i$ to be the super-tiling obtained by shifting ${𝕋}_0$ by the vector $(i,i)$ if $T$ is square, or by $(0,i\sqrt{3})$ if $T$ is triangular or hexagonal. These shifted super-tilings remain axis-aligned super-tilings of $T$, as all their vertices align with those of $T$.

Since we shift in a direction not aligned with any edge of $T$, and since $i\le f-1$, each edge or vertex of $T$ lies on the boundary of $O(1)$ faces across the family ${\{{𝕋}_i\}}_{i=0}^{f-1}$. It follows that for any discrete vertex set $V\subseteq V(T)$ with $|V|=k$, there exists some ${𝕋}_i$ such that only $O(k/f)$ vertices lie on boundaries of faces in ${𝕋}_i$. Therefore, there exists a super-tiling $𝕋\in \{{𝕋}_0,\mathrm{\dots },{𝕋}_{f-1}\}$ such that the total number of boundary vertices from $P$ and $Q$ is $O((n+m)/f)$, which implies $O((n+m)/f)=O(\sqrt{n+m})$ induced subpaths. To compute $𝕋$, we iterate over all vertices $v$ of $P$ and $Q$ and, for each, determine the $O(1)$ super-tilings ${𝕋}_i$ with $v\in B({𝕋}_i)$ by iterating over all $𝕋\in \{{𝕋}_0,\mathrm{\dots },{𝕋}_{f-1}\}$. This takes $O((n+m)f)$ total time. We then select the super-tiling ${𝕋}_i$ that minimizes $|(P\cup Q)\cap B({𝕋}_i)|$. $◀$

Let $𝕋$ be the computed super-tiling of $T$. We partition $P$ and $Q$ into induced subpaths, denoted by $S(P,𝕋)$ and $S(Q,𝕋)$. These $O(\sqrt{n+m})$ subpaths naturally induce a subdivision of the free-space diagram $M_{\mathrm{\Delta }}$ into $O(n+m)$ rectangular submatrices $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$, where $P[i:i^{\prime }]\in S(P,𝕋)$ and $Q[j:j^{\prime }]\in S(Q,𝕋)$ (see Figure 8(a)).

Our algorithm makes use of a wave-front method. We define a wave-front $W$ as a monotone walk through the grid $[1,n]\times [1,m]$ that separates $(1,1)$ from $(n,m)$. At each grid point $(i,j)\in W$, we store a Boolean value indicating whether there exists a monotone walk $F$ from $(1,1)$ to $(i,j)$ such that all points on $F$ lie in free space: that is, $M_{\mathrm{\Delta }}[x,y]=0$ for all $(x,y)\in F$ (Figure 8(b)).

An update to the wave-front $W$ selects a pair of subpaths $(P[i:i^{\prime }],Q[j:j^{\prime }])\in S(P,𝕋)\times S(Q,𝕋)$ such that the bottom and left facets of the submatrix $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$ lie on the current wave-front. The update removes these facets from $W$ and inserts the top and right facets instead. To perform the update, we consider the faces $F_P$ and $F_Q$ of $𝕋$ that $P[i:i^{\prime }]$, respectively $Q[j:j^{\prime }]$, are assigned to, and proceed via a case distinction:

1. 1.

   If $F_P$ and $F_Q$ are not aligned, then they are well-separated by a vertex $v$ (by Lemma 10), and we show how to perform a fast update using $v$.

2. 2.

   If $F_P$ and $F_Q$ are aligned, we perform a brute-force update and use a counting argument to bound the total running time of these updates.

We analyse both cases separately, observing that while some instances may involve only Case 1 or only Case 2 submatrices, we can independently bound the total cost for each case.

We show an update algorithm that is near-linear in the perimeter of the submatrix $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$.

By Lemma 10, the subcurves $P[i:i^{\prime }]$ and $Q[j:j^{\prime }]$ are well-separated by some vertex $v\in V(T)$, which we can identify in constant time. Given $v$, we compute two curves in $ℝ$ whose $\mathrm{\Delta }$-free space matrix equals $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$. We define these curves as follows.

For a point $p\in P[i:i^{\prime }]$ we let $\overline{p}=\mathrm{dist}(p,v)$. Likewise, for a point $q\in Q[j:j^{\prime }]$, we let $\overline{q}=-\mathrm{dist}(q,v)$. Note the difference in sign. Because $P[i:i^{\prime }]$ and $Q[j:j^{\prime }]$ are well-separated by $v$, we have $\mathrm{dist}(p,q)=\mathrm{dist}(p,v)+\mathrm{dist}(v,q)=|\overline{p}-\overline{q}|$ for any $p\in P[i:i^{\prime }]$ and $q\in Q[j:j^{\prime }]$. We let $\overline{P}=({\overline{p}}_i,\mathrm{\dots },{\overline{p}}_{i^{\prime }})$ and $\overline{Q}=({\overline{q}}_j,\mathrm{\dots },{\overline{q}}_{j^{\prime }})$.

The $\mathrm{\Delta }$-free-space matrix $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$ is equal to the $\mathrm{\Delta }$-free space matrix of the sequences $\overline{P}$ and $\overline{Q}$ over the real line under the absolute value metric. Let ${\overline{M}}_{\mathrm{\Delta }}$ be this matrix. We compute the top and right facets of ${\overline{M}}_{\mathrm{\Delta }}$ in $O(k\log k)$ time with existing fast algorithms for 1D separated sequences [8, 31]. $◀$

For aligned face pairs, we fall back on a brute-force update strategy based on switching cells, a concept introduced by Har-Peled, Knauer, Wang and Wenk. [4].

The switching cells in a submatrix $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$ allow for a direct update of the wave-front:

We apply the brute-force update algorithm to all subpath pairs $(P[i:i^{\prime }],Q[j:j^{\prime }])\in S(P,𝕋)\times S(Q,𝕋)$ whose associated faces $F_P$ and $F_Q$ in $𝕋$ are aligned. We now show that the total number of switching cells encountered in these submatrices is not too large:

Fix a vertex $p_i$ and let $F_p$ be a face of $𝕋$ such that $p_i\in \overline{F_p}$. Since $P$ and $Q$ are paths in a unit tiling, a switching cell $M_{\mathrm{\Delta }}[i,j]$ occurs only if $q_j$ lies at distance exactly $\mathrm{\Delta }$ from $p_i$.

Let $B_i(\mathrm{\Delta })\subseteq V(T)$ denote the set of all vertices at distance exactly $\mathrm{\Delta }$ from $p_i$. This set lies on the boundary of a shape whose geometry depends on the tiling type:

• $\mathrm{■}$

  $B_i(\mathrm{\Delta })$ is the boundary of a diamond if $T$ is a square tiling.

• $\mathrm{■}$

  $B_i(\mathrm{\Delta })$ is the boundary of a regular hexagon if $T$ is a triangular tiling.

• $\mathrm{■}$

  $B_i(\mathrm{\Delta })$ is the boundary of a (non-regular) hexagon if $T$ is a hexagonal tiling.

These regions are convex. Consider a face $F^{\prime }$ of $𝕋$ that is aligned with $F_p$. The intersection of $B_i(\mathrm{\Delta })$ with $\overline{F^{\prime }}$ contains at most $O(\sqrt{n+m})$ vertices. Each of these vertices could correspond to at most one vertex $q_j\in Q$ where $(i,j)$ is a switching cell. There are only $O(1)$ faces of $𝕋$ that are aligned with $F_p$, whose closures intersect $B_i(\mathrm{\Delta })$. Hence, there are at most $O(\sqrt{n+m})$ such $q_j$ values per $p_i$. Summing over all $n$ vertices of $P$ gives the desired $O(n\sqrt{n+m})$ bound.

What remains is to compute these pairs $(p_i,q_j)$. We preprocess $Q$ in a membership query data structure. For each $p_i\in P$, we select its assigned face $F_p$ in constant time and we identify the $O(1)$ faces $F^{\prime }$ of $𝕋$ that are aligned with $F_p$ and intersect $B_i(\mathrm{\Delta })$ in constant time. For every such face $F^{\prime }$, we iterate over the vertices $v$ in $\overline{F^{\prime }}\cap B_i(\mathrm{\Delta })$. We find if there exists a $q_j\in Q$ with $v=q_j$ in $O(\log m)$ time through a membership query. If so, then we compute $\mathrm{dist}(p_i,q_{j+1})$ and $\mathrm{dist}(p_i,q_{j-1})$ to determine whether $M_{\mathrm{\Delta }}[i,j]$ is a switching cell. $◀$ We are now ready to prove our main theorem:

Given $T$, $P$, and $Q$, we begin by applying Lemma 11 to compute in $O({(n+m)}^{1.5})$ time a super-tiling $𝕋$ and the corresponding subpaths $S(P,𝕋)$ and $S(Q,𝕋)$. The number of subpath pairs $(P[i:i^{\prime }],Q[j:j^{\prime }])\in S(P,𝕋)\times S(Q,𝕋)$ is $O(n+m)$. For each pair, we determine if the corresponding faces $F_P$ and $F_Q$ in $𝕋$ are aligned, which takes $O(n+m)$ total time.

The product set $S(P,𝕋)\times S(Q,𝕋)$ induces a grid of $O(n+m)$ rectangular submatrices of $M_{\mathrm{\Delta }}$ with $O(\sqrt{n+m})$ rows and columns. Thus:

Next, we initialize the wave-front $W$ by computing the first row and first column of $M_{\mathrm{\Delta }}$, i.e., all entries $M_{\mathrm{\Delta }}[i,1]$ for $i\in [n]$ and $M_{\mathrm{\Delta }}[1,j]$ for $j\in [m]$, in $O(n+m)$ time. We then iterate diagonally through all pairs $(P[i:i^{\prime }],Q[j:j^{\prime }])$ in $S(P,𝕋)\times S(Q,𝕋)$ and perform a wave-front update for each pair.

If the two faces $F_P$ and $F_Q$ of $𝕋$ assigned to $P[i:i^{\prime }]$ and $Q[j:j^{\prime }]$ are not aligned then we apply Lemma 12. The total time spent in this case equals:

By Equation 1, this sum is upper bound by $O({(n+m)}^{1.5}\log (n+m)$.

If the two faces $F_P$ and $F_Q$ of $𝕋$ assigned to $P[i:i^{\prime }]$ and $Q[j:j^{\prime }]$ are aligned then we apply Lemma 14 instead. The total time spent is:

The first term and second term are bounded by $O({(n+m)}^{1.5}\log (n+m))$ by Equation 1 and Lemmas 14+15, respectively. Once the wave-front $W$ reaches the entry $(n,m)$, we have determined whether ${\mathrm{D}}_{\mathrm{T}}(P,Q)\le \mathrm{\Delta }$, proving the theorem. $◀$

Given some $\mathrm{\Delta }\in ℝ$, we first show how to decide whether $D_F(P,Q)\le \mathrm{\Delta }$ using the wave-front propagation technique from Section 4, with suitable modifications for curves in the plane. Let $t>1$ be a parameter to be determined later. We define an axis-aligned square tiling $𝕋$ of the plane where each square has edge length $t$.

Note that $B(P,𝕋)$ may contain overlapping but distinct vertices of $P$ (since an $(\epsilon ,\delta )$-curve may visit the same point up to $\delta$ times). If we remove all edges from $P$ which intersect some edge of $𝕋$, we see that the breakpoints induce a partition of the vertices of $P$ into pairwise vertex-disjoint subcurves $P[i:i^{\prime }]$, each fully contained in the closure $\overline{F}$ of a face $F\in 𝕋$. We refer to these subcurves as the induced subcurves $S(P,𝕋)$ and we assign each induced subcurve to a face in $𝕋$. We prove that for a suitable choice of $𝕋$, the total number of induced subcurves satisfies $|S(P,𝕋)\cup S(Q,𝕋)|=O((n+m)/t)$.

We then apply our wave-front algorithm over the product set $S(P,𝕋)\times S(Q,𝕋)$. For a pair of subcurves $(P[i:i^{\prime }],Q[j:j^{\prime }])$, let $F_P$ and $F_Q$ denote their respective containing faces in $𝕋$. We distinguish two cases:

• $\mathrm{■}$

  If $F_P$ and $F_Q$ are not aligned, we show that $(P[i:i^{\prime }],Q[j:j^{\prime }])$ is well-separated by a corner of either $F_P$ or $F_Q$. We then apply Lemma 12 to perform a wave-front update in $O((i^{\prime }-i+j^{\prime }-j)\log (n+m))$ time.

• $\mathrm{■}$

  If $F_P$ and $F_Q$ are aligned, we apply the brute-force algorithm of Lemma 14, but with a more careful analysis of the number of switching cells.

Balancing the choice of $t$ is critical: a larger $t$ reduces the number of wave-front updates, while a smaller $t$ reduces the number of switching cells encountered. We choose $t$ to optimize the overall running time.

We construct a tiling $𝕋$ such that it creates few induced subcurves.

The proof mirrors that of Lemma 11. Let ${𝕋}_0$ be an axis-aligned square tiling with edge length $t$, and let ${𝕋}_i$ denote the tiling obtained by shifting ${𝕋}_0$ by $(i,i)$ for $i\in [t-1]$. We required that each edge $e$ of $P$ or $Q$ has length at most $\gamma \in O(1)$. Thus each edge intersects the boundary of at most $O(1)$ of the shifted tilings. It follows that there exists an index $i$ such that ${𝕋}_i$ induces only $O((n+m)/t)$ breakpoints across $P$ and $Q$.

To find ${𝕋}_i$, we iterate over all $O(n+m)$ edges of $P$ and $Q$. For each edge, we test for intersection with each of the $t$ candidate tilings in constant time. This gives an overall running time of $O((n+m)t)$ to find the tiling ${𝕋}_i$ that minimizes $|B(P,{𝕋}_i)\cup B(Q,{𝕋}_i)|$. $◀$

Unlike in Section 4, the subcurves in $S(P,𝕋)$ are vertex-disjoint. Thus, we never have a submatrix $M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$ whose bottom-left facet coincides with the current wave-front $W$. However, we can always find a submatrix $M^{\prime }:=M_{\mathrm{\Delta }}[i:i^{\prime },j:j^{\prime }]$ where each of the cells on the bottom-left facet of $M^{\prime }$ is adjacent to a cell in $W$. We extend $W$ to cover it in $O(i^{\prime }-i+j^{\prime }-j)$ time via brute force and thereby define wave-front updates analogously.

Our key observation is that, even though the edges of $P[i:i^{\prime }]$ and $Q[j:j^{\prime }]$ do not coincide with $𝕋$, a pair of faces $(F_P,F_Q)$ of $𝕋$ are still well-separated whenever they are not aligned:

Assume, without loss of generality, that the bottom-left corner of $F_P$ lies above and to the right of the top-right corner of $F_Q$. Then any shortest $L_1$ path from a point in $\overline{F_P}$ to one in $\overline{F_Q}$ may be rerouted through that corner. The rest follows from Lemma 12. $◀$

We upper bound the number of switching cells $M_{\delta }[i,j]$ where $p_i$ and $q_j$ lie in aligned faces of $𝕋$:

We preprocess $Q$ by snapping its vertices to a square grid $G$ of edge length ${\epsilon }^{-1}$, forming $Q^{\prime }$. Each vertex in $Q^{\prime }$ corresponds to $O(\delta )$ original vertices since $Q$ is an $(\epsilon ,\delta )$-curve. We store $Q^{\prime }$ in a spatial data structure (e.g., a lexicographically sorted balanced binary tree), where a query point $z$ returns all $q_j\in Q$ corresponding to $z$ in $O(\delta +\log n)$ time.

Recall that all edges of $Q$ have length at most $\gamma \in O(1)$. Fix a vertex $p_i$ and let $F_p$ be a face of $𝕋$ that contains $p_i$. Let $B_i(\mathrm{\Delta })$ be the metric circle (under the $L_1$ metric) of radius $\mathrm{\Delta }$ centred at $p_i$. Let $\mathrm{\Gamma }$ denote a ball with radius $2\gamma$ and $B_i^{\ast }(\mathrm{\Delta })$ be the metric annulus that is the Minkowski-sum $\mathrm{\Gamma }\oplus B_i(\mathrm{\Delta })$. Observe that an edge $(q_j,q_{j+1})$ of $Q$ intersects $B_i(\mathrm{\Delta })$ only if one of its corresponding vertices $q_j^{\prime }$ and $q_{j+1}^{\prime }$ of $Q^{\prime }$ lies in $B_i^{\ast }(\mathrm{\Delta })$.

There are $O(1)$ faces $F^{\prime }$ of $𝕋$ that are aligned with $F_p$ and that intersect $B_i^{\ast }(\mathrm{\Delta })$. Let $A:=B_i^{\ast }(\mathrm{\Delta })\cap F^{\prime }$. Distinguishing between $\mathrm{\Delta }>1$ and $\mathrm{\Delta }\le 1$, we see that $A$ has an area of $O(\max \{1,t\}\gamma )$ and therefore $A$ contains at most $O(\frac{\gamma \max \{1,t\}}{{\epsilon }^2})=O(\frac{t+1}{{\epsilon }^2})$ vertices of $G$. We iterate over the vertices in $B_i^{\ast }(\mathrm{\Delta })\cap \overline{F^{\prime }}\cap V(G)$ and for each we perform a membership query on $Q^{\prime }$. This returns $O(\frac{\delta (t+1)}{{\epsilon }^2})$ vertices of $Q^{\prime }$. For each reported vertex $q_j^{\prime }$ we test if $M_{\mathrm{\Delta }}[i,j]$ is a switching cell in constant time. Thus, for any $p_i\in P$, we compute all switching cells $M_{\mathrm{\Delta }}[i,j]$ that correspond to the lemma statement in $O(\frac{\delta (t+1)}{{\epsilon }^2}\log m)$ time. $◀$