A Near-Linear Time Exact Algorithm for the $L_1$-Geodesic Fréchet Distance Between Two Curves on the Boundary of a Simple Polygon

In this section, we consider the setting where $R$ and $B$ are $x$-monotone curves in ${ℝ}^2$, separated by a horizontal line. We give a simple partition algorithm for the parameter space of $R$ and $B$ that yields a doubly-separated partition of cost $𝒪((n+m)\log nm)$:

Next we reduce the following setting to that of two vertically-separated $x$-monotone curves: Let $P$ be a simple polygon, and let $R$ and $B$ be two simple curves on the boundary of $P$, separated by a horizontal line segment in $P$. That is, there exists a horizontal line segment $e^{\ast }$ in $P$, such that splitting $P$ at $e^{\ast }$ creates two subpolygons where $R$ and $B$ lie in different subpolygons.²²2We consider $e^{\ast }$ to be part of both subpolygons. Recall that we assume $R$ to be oriented clockwise with respect to $P$, and $B$ counter-clockwise. We construct a pair of vertically-separated $x$-monotone curves whose $\delta$-free space (under the $L_1$-norm) is identical to that of $R$ and $B$, for all $\delta$.

Every $L_1$-geodesic between points $r\in R$ and $b\in B$ intersects $e^{\ast }$ in exactly one line segment. Moreover, there exists an $L_1$-geodesic that is composed of the following three parts: an $L_1$-geodesic between $r$ and its closest point $u$ on $e^{\ast }$, an $L_1$-geodesic between $b$ and its closest point $v$ on $e^{\ast }$, and the line segment $\overline{uv}$. For two vertically-separated $x$-monotone curves (as in Section 3.1), there exists a similar shortest path between two points, namely one that is composed of two vertical segments and a horizontal segment on the separator. We use this connection for our reduction, which we specify next.

We refer to the “projection” of a point $p\in P$ onto $e^{\ast }$ (with slope other than $\pm 1$) as the point on $e^{\ast }$ closest to $p$, and we denote this projection by $\mathrm{𝑁𝑁}(p)$. Above we established that between any two points $r\in R$ and $b\in B$, there exists an $L_1$-geodesic that goes through the projections $\mathrm{𝑁𝑁}(r)$ and $\mathrm{𝑁𝑁}(b)$. We introduce two real-valued functions, which we use to define the coordinates of the $x$-monotone curves we reduce the problem to.

We assume $e^{\ast }$ is parameterized over $[1,2]$. The first function, $\phi :P\to [1,2]$, indexes the projections on $e^{\ast }$ of the points in $P$. That is, $e^{\ast }(\phi (p))=\mathrm{𝑁𝑁}(p)$. The second function, $\psi :P\to [1,2]$, represents the distance function from points to their projections, so $\psi (p)=\overline{d}(p,\mathrm{𝑁𝑁}(p))$.

We consider the curves $\overline{R}:[0,1]\to {ℝ}^2$ and $\overline{B}:[0,1]\to {ℝ}^2$ given by $\overline{R}(x)=(\phi (R(x)),\psi (R(x)))$ and $\overline{B}(y)=(\phi (B(y)),-\psi (B(y)))$. Note that $\overline{d}(R(x),B(y))={\parallel \overline{R}(x)-\overline{B}(y)\parallel }_1$ for all $x,y\in {[0,1]}^2$, and so ${ℱ}_{\delta }(R,B)={ℱ}_{\delta }(\overline{R},\overline{B})$ for all $\delta$. The curves are separated by the horizontal line $(-\mathrm{\infty },\mathrm{\infty })\times \{0\}$. Next we prove that the curves are $x$-monotone, making the algorithm developed in Section 3.1 applicable to them:

We have shown that the algorithm developed in Section 3.1 can be applied to the curves $\overline{R}$ and $\overline{B}$. Next we show that $\overline{R}$ and $\overline{B}$ have low complexity. Let $R$ have $n$ vertices and $B$ have $m$ vertices. We show that $\overline{R}$ has $𝒪(n)$ vertices and $\overline{B}$ has $𝒪(m)$ vertices. While doing so, we develop a data structure that can construct $\overline{R}$ and $\overline{B}$ efficiently.

We construct pieces of $\overline{R}$ and $\overline{B}$ by computing the functions $\phi$ and $\psi$ over individual edges of $R$ and $B$. When restricted to a single line segment $e$, the function $\psi$ is similar to the “hourglass function” $H_{e,e^{\ast }}$ introduced by Cook and Wenk [9]. The hourglass function uses the $L_2$-norm to measure lengths of shortest paths, and can have $𝒪(k)$ complexity [9]. Perhaps surprisingly however, we show that since we measure lengths with the $L_1$-norm, the function $\psi$ has only constant complexity when applied to a single edge. Moreover, the function $\phi$ has constant complexity as well.

By querying the data structure of Lemma 5 with every edge of $R$ and $B$ individually and combining the results, we obtain the functions $\phi$ and $\psi$ over $R$ and $B$ in $𝒪((n+m)\log k)$ time, after $𝒪(k)$-time preprocessing. From this, we extract $\overline{R}$ and $\overline{B}$ in $𝒪(n+m)$ additional time. The complexities of $\overline{R}$ and $\overline{B}$ are $𝒪(n)$ and $𝒪(m)$, respectively. Thus we obtain:

In this section, we start out in the general setting, where $R$ and $B$ are simple, interior-disjoint curves on the boundary of a simple polygon $P$, and construct a doubly-separated partition of the parameter space of $R$ and $B$.

We follow the approach of Section 3.1, in that we partition the parameter space recursively, though this time based on horizontal chords of $P$. A chord is a maximal segment that does not go outside $P$. By our assumptions, a chord can have at most three points in common with the boundary of $P$. If possible, we will use bichromatic chords, which have a point in common with both curves. Each such chord $e^{\ast }$ splits each curve into at most three subcurves: If $e^{\ast }$ intersects $R$ only at an endpoint of $R$, the chord “trivially” splits $R$ into the curve $R$ itself. Otherwise, $R$ is split into the maximal prefix $R[0,x]$ whose intersection with $e^{\ast }$ is only the point $R(x)$, the maximal suffix $R[x^{\prime },1]$ whose intersection with $e^{\ast }$ is only the point $R(x^{\prime })$, and the maximal subcurve $R[x,x^{\prime }]$ bounded by $e^{\ast }$. See Figure 5. The split of $B$ induced by $e^{\ast }$ is defined analogously, but if $R$ is split into three subcurves, then $B$ can be split into at most two subcurves (and vice versa). A chord corresponds to a partition of the parameter space into the axis-aligned rectangles whose corresponding subcurves are induced by the splits of $R$ and $B$. Thus, a chord corresponds to a partition into at most six regions.

If a bichromatic chord does not exist, then $R$ and $B$ can be separated trivially by a horizontal chord. Our partition algorithm works recursively, like the algorithm of Lemma 3. To bound the recursive depth, we use a chord that splits $R$ and $B$ into at most two and three subcurves each, where the first and last subcurves of each have a total of at most $(n+m)/c$ vertices at either side of the chord, for some constant $c>1$.

We prove the existence of a horizontal chord with the desired properties, and give a construction algorithm. The result follows from a relaxed version of the “polygon-cutting theorem” of Chazelle [6].

With the existence and construction result for good chords at hand, we make an initial partition of the parameter space. The partition is not yet a doubly-separated partition, but we refine it afterwards into one that is.

We recursively partition the parameter space as follows. If $|R|\le 2$ and $|B|\le 2$ then we stop partitioning further. Otherwise, we compute a horizontal chord $e^{\ast }$ of $P$ with the algorithm of Lemma 8, taking $𝒪(k)$ time.

Assuming $P$ is in general position, the chord intersects one curve in at most two points and the other in at most one point. Suppose that $e^{\ast }$ intersects $R$ in two points, splitting it into the subcurves $R_1=R[0,x]$, $R_2=R[x,x^{\prime }]$ and $R_3=R[x^{\prime },1]$, and that $e^{\ast }$ intersects $B$ in one point, splitting it into the subcurves $B_1=B[0,y]$ and $B_2=B[y,1]$. These five subcurves together define six axis-parallel rectangles in the parameter space, which is the partition corresponding to $e^{\ast }$.

Let $𝒫$ be this partition. The subcurve $R_2$ is bounded by $e^{\ast }$, and thus is separated from all of $B$ by $e^{\ast }$. Further, the subcurve $R_1$ is separated from $B_2$, and the subcurve $R_3$ from $B_1$. Thus the only regions in the partition whose corresponding subcurves are not separated by a horizontal chord are the bottom-left region $[0,x]\times [0,y]$ and the top-right region $[x^{\prime },1]\times [y,1]$; we recursively partition $𝒫$ in these regions.

We analyze the partition in the same manner as we do for doubly-separated partitions. That is, we refer to the cost of an axis-aligned rectangle $ℛ=[x,x^{\prime }]\times [y,y^{\prime }]$ as $\mathrm{Cost}(ℛ)=\left|R[x,x^{\prime }]\right|+\left|B[y,y^{\prime }]\right|$, the same as for doubly-separated regions, and refer to the cost of the partition $𝒫$ as $\mathrm{Cost}(𝒫)={\sum }_{ℛ\in 𝒫}\mathrm{Cost}(ℛ)$.

We refine $𝒫$ into a doubly-separated partition. Some regions in $𝒫$ already correspond to line segments on $R$ and $B$, and so are trivial. The other regions correspond to subcurves of $R$ and $B$ that are separated by a horizontal chord of $P$. We partition these regions further using the result of Corollary 7.

We present an algorithm for deciding whether ${\overline{d}}_{\mathrm{F}}(R,B)\le \delta$ for a given parameter $\delta \ge 0$. Our algorithm decides whether a bimonotone path in ${ℱ}_{\delta }(R,B)$ exists from $(0,0)$ to $(1,1)$. Let ${𝒫}^{\ast }$ be a doubly-separated partition of the parameter space of $R$ and $B$ computed with the algorithm of Lemma 10. We propagate reachability information through each region in ${𝒫}^{\ast }$ separately.

Before we do so, we need to address one issue. For the regions $ℛ\in {𝒫}^{\ast }$ where we have a pair of doubly-separated $x$-monotone curves $\overline{R}$ and $\overline{B}$ whose free space is identical to that inside $ℛ$, we wish to apply the result of Lemma 2. However, this algorithm is for propagating reachability from a given discrete set of points to a given discrete set of points. Hence we first construct sets $S_{ℛ}$ and $T_{ℛ}$ to which we apply the result of Lemma 2.

We define the sets $S_{ℛ}$ and $T_{ℛ}$. For this, we say that a point $B(x)$ is locally closest to $R(y)$ if an infinitesimal perturbation of $B(x)$ while staying on $B$ increases its distance to $R(y)$. We call points on $R$ locally closest to points on $B$ if a symmetric condition holds. The set $T_{ℛ}$ is the set of all points $(x^{\ast },y^{\ast })$ on the top and right sides of $ℛ$ for which at least one of $R(x^{\ast })$ and $B(y^{\ast })$ is a vertex of $R$ or $B$, or locally closest to the other point.

Let $ℛ=[x,x^{\prime }]\times [y,y^{\prime }]\in {𝒫}^{\ast }$. The set $T_{ℛ}$ is defined as follows. For each edge $e$ of $R$, we add the point $(x^{\ast },y^{\prime })$ to $T_{ℛ}$ if $x^{\ast }\in [x,x^{\prime }]$ and $R(x^{\ast })$ is either a vertex of $R$ or the point on $e$ closest to $B(y^{\prime })$. Symmetrically, for each edge $e$ of $B$, we add the point $(x^{\prime },y^{\ast })$ to $T_{ℛ}$ if $y^{\ast }\in [y,y^{\prime }]$ and $B(y^{\ast })$ is either a vertex of $B$ or the point on $e$ closest to $R(x^{\prime })$.

The set $S_{ℛ}$ is defined as all points in $S\cap ℛ$, as well as all points on the bottom and left sides of $ℛ$ that are in a set $T_{{ℛ}^{\prime }}$ (for an adjacent region ${ℛ}^{\prime }$) and are $\delta$-reachable from $S_{{ℛ}^{\prime }}$. The set $S_{ℛ}$ is defined as all points on the bottom and left sides of $ℛ$ that are in a set $T_{{ℛ}^{\prime }}$ (for an adjacent region ${ℛ}^{\prime }$) and are $\delta$-reachable from $S_{{ℛ}^{\prime }}$. If $ℛ$ contains the point $(0,0)$, we set $S_{ℛ}=\{(0,0)\}$ instead.

The usefulness of these sets comes from Lemma 11, from which it follows that matchings can be assumed to enter and leave a region $ℛ$ through points in $S_{ℛ}$ and $T_{ℛ}$, respectively.

Naturally, for our decision algorithm, we need to compute these sets efficiently:

We are now ready to give our decision algorithm, which decides whether a bimonotone path in ${ℱ}_{\delta }(R,B)$ from $(0,0)$ to $(1,1)$ exists, for a given $\delta \ge 0$. First, we compute the doubly-separated partition ${𝒫}^{\ast }$ of Lemma 10, taking $𝒪(k\log nm+(n+m){\log }^{2}nm)$ time. The partition has cost $𝒪((n+m){\log }^{2}nm)$, and for each region $[x,x^{\prime }]\times [y,y^{\prime }]$ in this partition, either $R[x,x^{\prime }]$ and $B[y,y^{\prime }]$ are line segments, or we have additionally computed a pair of doubly-separated $x$-monotone curves $\overline{R}$ and $\overline{B}$ with $𝒪(\left|R[x,x^{\prime }]\right|)$ and $𝒪(\left|B[y,y^{\prime }]\right|)$ vertices, respectively. We compute the sets $T_{ℛ}$ for all regions $ℛ\in {𝒫}^{\ast }$, taking $𝒪(k+(n+m){\log }^{2}nm\log k)$ time. The goal is then to compute, for each set $T_{ℛ}$, the subset of points that are $\delta$-reachable from $(0,0)$.

Consider a region $ℛ=[x,x^{\prime }]\times [y,y^{\prime }]\in {𝒫}^{\ast }$ and suppose that for each region ${ℛ}^{\prime }$ incident to the bottom or left side of $ℛ$ we have already computed the subset of $T_{{ℛ}^{\prime }}$ of points that are $\delta$-reachable from $(0,0)$. The union of these subsets forms the set $S_{ℛ}$ that serves as the set of “entrances” for $ℛ$; a point in $T_{ℛ}$ is $\delta$-reachable from $(0,0)$ if and only if it is $\delta$-reachable from a point in $S_{ℛ}$.

If $R[x,x^{\prime }]$ or $B[y,y^{\prime }]$ has more than one edge, we have available a pair of doubly-separated $x$-monotone curves $\overline{R}$ and $\overline{B}$ with ${ℱ}_{\delta }(R[x,x^{\prime }],B[y,y^{\prime }])={ℱ}_{\delta }(\overline{R},\overline{B})$. We apply the algorithm of Lemma 2 to these curves, using the set $S_{ℛ}$ for the “entrances” and the set $T_{ℛ}$ for the “potential exits.” This algorithm reports all points in $T_{ℛ}$ that are $\delta$-reachable from at least one point in $S_{ℛ}$ in $𝒪((|\overline{R}|+|\overline{B}|)\log |\overline{R}||\overline{B}|)=𝒪(\mathrm{Cost}(ℛ)\log \mathrm{Cost}(ℛ))$ time.

If both $R[x,x^{\prime }]$ and $B[y,y^{\prime }]$ are line segments, then we can check in constant time whether a given point in $T_{ℛ}$ is reachable from a given point in $S_{ℛ}$, so we can report the set of points in $T_{ℛ}$ that are $\delta$-reachable from at least one point in $S_{ℛ}$ in $𝒪(|S_{ℛ}|\cdot |T_{ℛ}|)=𝒪(1)$ time.

We now have an algorithm that, given the sets $S_{ℛ}$ and $T_{ℛ}$, reports the points in $T_{ℛ}$ that are $\delta$-reachable in $𝒪(\mathrm{Cost}(ℛ)\log \mathrm{Cost}(ℛ))$ time. Applying this algorithm to all regions in ${𝒫}^{\ast }$, in some topological order, we eventually decide whether $(1,1)$ is $\delta$-reachable from $(0,0)$, since it is included in a set $T_{ℛ}$. This takes

time. The computations of ${𝒫}^{\ast }$ and the sets $T_{ℛ}$, which took $𝒪(k\log nm+(n+m){\log }^{2}nm\log k)$ time in total, dominate the running time. However, these computations are independent of the decision parameter $\delta$, and so we view these computations as preprocessing. This gives the following result:

In this section, we turn the decision algorithm of the previous section into an algorithm that computes ${\overline{d}}_{\mathrm{F}}(R,B)$, at the cost of a logarithmic factor in the running time when compared to the decision algorithm. For this, we derive a polynomial number of candidate distances, one of which is the actual Fréchet distance ${\overline{d}}_{\mathrm{F}}(R,B)$. Specifically, for two sets of real numbers $X$ and $Y$, their Cartesian sum, denoted $X\oplus Y$, is the multiset $X\oplus Y=\{\{x+y\mid x\in X,y\in Y\}\}$. We will show that we can compute two sets $X$ and $Y$ of $𝒪((n+m){\log }^{2}nm)$ real numbers each, such that ${\overline{d}}_{\mathrm{F}}(R,B)\in X\oplus Y$. After computing $X$ and $Y$ in near-linear time, we can use existing techniques [8, 10] for selection in Cartesian sums to binary search over the Cartesian sum $X\oplus Y$ without explicitly computing its $|X|\cdot |Y|$ many elements.

We again make use of the doubly-separated partition ${𝒫}^{\ast }$ computed with the algorithm of Lemma 10. Additionally, we again use the sets $T_{ℛ}$ for regions $ℛ\in {𝒫}^{\ast }$. Recall that there exists a Fréchet matching between $R$ and $B$ that corresponds to a bimonotone path in the parameter space that, for each region $ℛ\in {𝒫}^{\ast }$ that it intersects, goes through a point in $T_{ℛ}$. Thus, there exists a pair of points $s\in T_{{ℛ}^{\prime }}$ and $t\in T_{ℛ}$, for a region ${ℛ}^{\prime }$ and region $ℛ$ incident to the top or right side of ${ℛ}^{\prime }$, such that the minimum parameter $\delta$ for which there exists a $\delta$-matching from $s$ to $t$ is the Fréchet distance.

Take regions ${ℛ}^{\prime }$ and $ℛ$, with $ℛ$ incident to the top or right side of ${ℛ}^{\prime }$. Let $s\in T_{{ℛ}^{\prime }}$ and let $t\in T_{ℛ}$ be above and to the right of $s$. Let ${\delta }^{\ast }$ be the minimum parameter for which there exists a ${\delta }^{\ast }$-matching from $s$ to $t$. We construct sets $X_{ℛ}$ and $Y_{ℛ}$ such that ${\delta }^{\ast }\in X_{ℛ}\oplus Y_{ℛ}$.

If the subcurves corresponding to $ℛ$ both are line segments, then from Lemma 13 we obtain that $t$ is $\delta$-reachable from $s$, for some $\delta \ge 0$, if and only if both points lie in ${ℱ}_{\delta }(R,B)$. We set $X_{ℛ}$ to be the set minimum values $\delta$ for which points $t\in T_{ℛ}$ lie in ${ℱ}_{\delta }(R,B)$. The set $Y_{ℛ}$ is simply set to $\{0\}$. Taken over all regions in ${𝒫}^{\ast }$, the sets have a total cardinality of $𝒪(\mathrm{Cost}({𝒫}^{\ast }))=𝒪((n+m){\log }^{2}nm)$.

If one of the subcurves corresponding to $ℛ$ has more than one edge, then we have access to a pair of doubly-separated $x$-monotone curves whose $\delta$-free space is identical to the $\delta$-free space of $R$ and $B$ inside $ℛ$. Moreover, by Lemma 1, we can transform these curves into a pair of curves in $ℝ$ that are separated by the point $0$, such that the $\delta$-free space remains the same. Let $\overline{R}$ and $\overline{B}$ be these curves. Alt and Godau [2] observe that ${\delta }^{\ast }$ must be one of the following values:

• $\mathrm{■}$

  the minimum value for which $s$ and $t$ lie in ${ℱ}_{{\delta }^{\ast }}(\overline{R},\overline{B})$, or

• $\mathrm{■}$

  the distance between a vertex of $\overline{R}$ (resp. $\overline{B}$) and an edge of $\overline{B}$ (resp. $\overline{R}$), or

• $\mathrm{■}$

  the distance between two vertices of $\overline{R}$ (resp. $\overline{B}$) to an edge of $\overline{B}$ (resp. $\overline{R}$), if the vertices lie at equal distance to the edge.

Since $\overline{R}$ and $\overline{B}$ are curves in $ℝ$ that are separated by a point, the candidates for ${\delta }^{\ast }$ of second and third type coincide. Moreover, the distance from a vertex $p$ of one curve to an edge $e$ of the other curve is also the distance from $p$ to the endpoint of $e$ closest to $p$, which must be a vertex. Thus, the latter two types of candidates for ${\delta }^{\ast }$ can be summarized as all pairwise distances between vertices of $\overline{R}$ and vertices of $\overline{B}$. Exploiting the separation of $\overline{R}$ and $\overline{B}$ further, the pairwise distances between vertices of $\overline{R}$ and vertices of $\overline{B}$ can be represented by the Cartesian sum of two sets $\overline{X}$ and $\overline{Y}$, containing the absolute values of the vertex values of $\overline{R}$ and $\overline{B}$, respectively. We set $X_{ℛ}\leftarrow \overline{X}$ and $Y_{ℛ}\leftarrow \overline{Y}$. Taken over all regions in ${𝒫}^{\ast }$, the sets have a total cardinality of $𝒪(\mathrm{Cost}({𝒫}^{\ast }))=𝒪((n+m){\log }^{2}nm)$.

Let $X={\bigcup }_{ℛ\in {𝒫}^{\ast }}{X}_{ℛ}$ and $Y={\bigcup }_{ℛ\in {𝒫}^{\ast }}{Y}_{ℛ}$. These sets have a total cardinality of $𝒪((n+m){\log }^{2}nm)$, and contain values $x^{\ast }\in X$ and $y^{\ast }\in Y$ such that ${\overline{d}}_{\mathrm{F}}(R,B)=x^{\ast }+y^{\ast }$. Next we search over $X\oplus Y$ to find the exact value of ${\overline{d}}_{\mathrm{F}}(R,B)$.

After sorting $X$ and $Y$, we can compute the $i^{\mathrm{th}}$ smallest value in $X\oplus Y$, for any given $i$, in $𝒪(|X|+|Y|)=𝒪((n+m){\log }^{2}nm)$ time [8, 10]. There are $|X|\cdot |Y|$ values in $X\oplus Y$. We binary search over the integers $1,\mathrm{\dots },|X|\cdot |Y|$, and at each considered integer $i$, we compute the $i^{\mathrm{th}}$ smallest value $\delta$ in $X\oplus Y$. Then we use our decision algorithm to decide whether ${\overline{d}}_{\mathrm{F}}(R,B)\le \delta$ and to guide the search to the value ${\delta }^{\ast }\in X\oplus Y$ with ${\delta }^{\ast }={\overline{d}}_{\mathrm{F}}(R,B)$.

In the above search procedure, each step takes $𝒪((n+m){\log }^{3}nm)$ time after preprocessing $P$ and the curves $R$ and $B$ for decision queries, which takes $𝒪(k\log nm+(n+m){\log }^{2}nm\log k)$ time (Lemma 14). We perform $𝒪(\log (|X|\cdot |Y|))=𝒪(\log nm)$ steps. Thus we obtain our main result: