\hideLIPIcs

University of Bonn, Bonn, [email protected]://orcid.org/0000-0002-8259-1187Partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 313421352 (FOR 2535 Anticipating Human Behavior). Affiliated with Lamarr Institute for Machine Learning and Artificial Intelligence. Hausdorff Center for Mathematics, University of Bonn, [email protected]://orcid.org/0000-0002-1943-2589Affiliated with Lamarr Institute for Machine Learning and Artificial Intelligence. Hausdorff Center for Mathematics, University of Bonn, Bonn, [email protected] funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 459420781. \CopyrightJacobus Conradi, Anne Driemel, Benedikt Kolbe \ccsdesc[500] Theory of computation Design and analysis of algorithms

Revisiting the Fréchet distance between piecewise smooth curves

Jacobus Conradi Anne Driemel Benedikt Kolbe

Abstract

Since its introduction to computational geometry by Alt and Godau in 1992, the Fréchet distance has been a mainstay of algorithmic research on curve similarity computations. The focus of the research has been on comparing polygonal curves, with the notable exception of an algorithm for the decision problem for planar piecewise smooth curves due to Rote (2007). We present an algorithm for the decision problem for piecewise smooth curves that is both conceptually simpler and naturally extends to the first algorithm for the problem for piecewise smooth curves in $\mathbb{R}^{d}$ .

We assume that the algorithm is given two continuous curves, each consisting of a sequence of $m$ , resp. $n$ , smooth pieces, where each piece belongs to a sufficiently well-behaved class of curves, such as the set of algebraic curves of bounded degree. We introduce a decomposition of the free space diagram into a controlled number of pieces that can be used to solve the decision problem similarly to the polygonal case, in $O(mn)$ time, leading to a computation of the Fréchet distance that runs in $O(mn\log(mn))$ time.

Furthermore, we study approximation algorithms for piecewise smooth curves that are also $c$ -packed for some fixed value $c$ . We adapt the existing framework for $(1+\varepsilon)$ -approximations and show that an approximate decision can be computed in $O(cn/\varepsilon)$ time for any $\varepsilon>0$ .

keywords:

Fréchet distance, piecewise smooth curves, decision algorithm

1 Introduction and motivation

The Fréchet distance is a well-studied distance measure between curves, with a long history in both applications and algorithmic research. The wealth of work surrounding the analysis of algorithms for computing the Fréchet distance is centered primarily on polygonal curves. However, more complicated curves and especially splines have become commonplace in industrial applications for, e.g., computer graphics, robotics and to represent motion tracking or planning data. In such applications, the number of dimensions corresponds to the number of tracked parameters, leading to a high-dimensional ambient space. On the other hand, polygonal curves in applications often represent (unnecessarily complex) discretizations approximating an underlying smooth curve that can be described more efficiently as a smooth curve using only a small number of parameters. For an algorithmic example, smooth curves may help in more naturally describing the average of a set of polygonal curves. A crucial prerequisite to using smooth curves similarly to polygonal curves in such contexts is the ability to effectively answer elementary algorithmic questions for such curves. A natural and fundamental task in computational geometry is therefore to devise algorithms for the computation of the Fréchet distance between smooth curves such as splines. Despite this, as far as we know, there is no known approach to realizing such a computation for curves in $\mathbb{R}^{d}$ . To tackle the case of smooth curves in the plane ( $d=2$ ), Rote [13] introduced an approach based on analyzing the turning angle and planar curvature of the planar curves. However, this approach does not easily generalize to higher dimensions. We revisit this problem and present a novel, simpler approach, with the additional benefit that it works for higher dimensions, with the same time complexity. Our methods are conceptually simple, but rely on a number of key technical ingredients.

Problem definition

Throughout the paper, $\gamma_{1}$ and $\gamma_{2}$ will be used to denote two piecewise smooth curves in $\mathbb{R}^{d}$ with $d$ fixed, that is, continuous maps $\gamma_{1},\gamma_{2}:[0,1]\to\mathbb{R}^{d}$ that are comprised of $m$ and $n$ smooth pieces, each of class $C^{2}$ . Let $A_{[0,1]}$ be the set of continuous and bijective maps $\alpha:[0,1]\to[0,1]$ that are increasing. The Fréchet distance between $\gamma_{1}$ and $\gamma_{2}$ is defined as $\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2}):=\inf\limits_{\alpha,\beta\in A_{[0,1]}}\max\limits_{t\in[0,1]}\|\gamma_{1}(\alpha(t))-\gamma_{2}(\beta(t))\|$ . Our methods naturally allow any fixed $\ell_{p}$ norm with $1<p<\infty$ for the norm $\|\cdot\|$ (the cases $p=1,\infty$ , while possible, would add a level of technicality to our treatment that distracts from its relative simplicity). To compute $\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2})$ , we mostly focus on the decision problem of deciding whether the Fréchet distance between two piecewise smooth curves is at most a given $\delta>0$ .

Results

Our first main contribution is that we establish an algorithm to solve the decision problem for the Fréchet distance between piecewise smooth curves. Assuming that the curves are algebraically bounded curves, i.e., piecewise smooth algebraic curves where the degree of the curves is bounded by a constant, we obtain a bound of $O(mn)$ for the time complexity of the decision problem, which matches the polygonal case. The running time is independent of the ambient dimension but the algebraic complexity of the operations involved in the algorithm depends on the dimension and the nature of the curves. Our algorithm for the decision problem results in an algorithm for the computation of the Fréchet distance for algebraically bounded curves in $O(mn\log(mn))$ time using parametric search, similarly to the polygonal case.

It is known [4] that the decision problem cannot be solved in strongly subquadratic time, so research has focused on investigating algorithms for restricted classes of curves. Our second contribution is that we show that we can adapt the framework from [7] for an efficient $(1+\epsilon)$ -approximation algorithm for the Fréchet distance between two $c$ -packed, polyognal curves to the setting of $c$ -packed piecewise smooth curves in $\mathbb{R}^{d}$ . To this end, we introduce a simplification procedure for piecewise smooth curves and distill the necessary ingredients to obtain a linear time decision algorithm for algebraically bounded $c$ -packed curves.

Comparison to previous work

To arrive at an algorithm for the decision problem for smooth planar curves for the $\ell_{2}$ -norm for a given $\delta$ in general position, Rote uses a partitioning of the smooth curves to obtain pieces for which the associated free space diagram $\mathrm{FSD}_{\delta}$ (Section 2) is well-behaved. His approach relies on analyzing the curves $\gamma_{1}$ and $\gamma_{2}$ , introducing cuts to control the turning angle and at points with a certain value for the planar curvature. In contrast to this, our approach is to analyze the free space diagram directly, by studying the boundary of the free space $\mathcal{D}_{\delta}$ in $\mathrm{FSD}_{\delta}$ . The free space is defined as the set of parameter value pairs at which the curves are at most a distance of $\delta$ apart. Working directly with the free space not only leads to a conceptually simpler algorithm, but also avoids relatively complicated integral equations related to the curvature and the turning angle. We propose a refined decomposition of each cell of $\mathrm{FSD}_{\delta}$ into a controlled number (depending on the degree of the curves) of subcells (Section 2), for which the existence of a monotone path connecting two intervals on the boundary of a subcell can be read off. Here, the role of convexity of the free space in a cell for polygonal curves is replaced by monotonicity of the boundary curves of $\mathcal{D}_{\delta}$ within each subcell of the refined decomposition. We emphasize here that our construction of the refined decomposition exclusively accesses the same values that are also required in Rote’s work to process each subcell of $\mathrm{FSD}_{\delta}$ .

Unlike the polygonal case, the free space within a cell of $\mathrm{FSD}_{\delta}$ can be very complicated, as illustrated by a contour plot of the distance function in parameter space for two degree 3 splines in $\mathbb{R}^{3}$ in Figure 1 for different values of $\delta$ .

Refer to caption — Figure 1: Two smooth curves in $\mathbb{R}^{3}$ and a contour plot of the associated distance function in the joint parametric space of the curves.

Figure 2 shows another example of the kind of behavior of the free space one can expect within a cell.

We note that both Rote’s decision algorithm as well as ours assume values of $\delta$ for which the boundary of $\mathcal{D}_{\delta}$ has no singularities. A key technical result we show (Section 3) is that singularities of the boundary of $\mathcal{D}_{\delta}$ are confined to a small number of critical values of $\delta$ and are not necessary for the computation of $\mathrm{d}_{\mathcal{F}}$ . Together with the approximation schemes for smooth curves we introduce later on, our results show that the setting of smooth curves provides a natural extended framework for algorithmic approaches to the Fréchet distance.

Computational model

We make the same assumptions as Rote in his work on planar smooth curves, subsuming the real RAM model. In essence, we assume that we can compare two real solutions of an algebraic equation. Specifically, we require being able to compute the intersection of a curve with a sphere of a given radius centered at a point of another curve and find the parameter values in $[0,1]$ that correspond to the intersections. While we limit the use of such algebraic operations where possible, our approach to the decision problem via construction of a specific partitioning of the free space diagram, the subsequent computation of $\mathrm{d}_{\mathcal{F}}$ , as well as the simplification ultimately make use of this assumption. Studying the algebraic numbers involved in the computations for different classes of curves goes beyond the scope of this paper.

2 A combinatorial description of the free space diagram

For two piecewise smooth curves $\gamma_{1},\gamma_{2}:[0,1]\to\mathbb{R}^{d}$ consisting of $m$ and $n$ pieces, respectively, and $\delta>0$ , the free space $\mathcal{D}_{\delta}=\mathcal{D}_{\delta}(\gamma_{1},\gamma_{2})$ is defined as

\mathcal{D}_{\delta}(\gamma_{1},\gamma_{2})=\left\{(x,y)\in[0,1]^{2}|\|\gamma_{1}(x)-\gamma_{2}(y)\|\leq\delta\right\}.

The complement of $\mathcal{D}_{\delta}$ in $[0,1]^{2}$ is commonly referred to as the forbidden region.

There is a natural partition of the joint parameter space $[0,1]^{2}$ of both curves into $m\cdot n$ rectangular cells such that $\gamma_{1}$ and $\gamma_{2}$ are smooth when restricting to the interior of each rectangle. We refer to the resulting decomposition of $[0,1]^{2}$ together with the partitioning into the free space and forbidden region as the free space diagram $\mathrm{FSD}_{\delta}$ . The primary motivation behind the introduction of the free space diagram is the elementary observation that $\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2})\leq\delta$ iff there is a path from $(0,0)$ to $(1,1)$ through the free space in $[0,1]^{2}$ that is monotone in both coordinates.

2.1 Overview of the algorithm

Similarly to the classical polygonal case, to solve the decision problem, we investigate the existence of a monotone (in both coordinates) path from $(0,0)$ to $(1,1)$ in the free space $\mathcal{D}_{\delta}$ . To this end, we refine the free space diagram using the boundary $B_{\delta}$ of the free space. Our decision algorithm has the following high-level description.

1.

Mark the minima and maxima of the boundary $B_{\delta}$ of the free space in $\mathrm{FSD}_{\delta}$ in the $x$ (horizontal) and $y$ (vertical) direction.
2.

Cut each cell of $\mathrm{FSD}_{\delta}$ into subcells, horizontally (vertically) through each marked point if it has a vertical (horizontal) tangent. Mark each point of intersection of a cut with $B_{\delta}$ .
3.

For each resulting subcell, pair the marked points on the boundary according to how they are connected by $B_{\delta}$ through monotone arcs, so that adjacent points are paired.
4.
Solve the decision problem for $\mathrm{FSD}_{\delta}$ using only the marked points and pairings by computing reachable intervals on the boundaries of cells, in particular
1. (a)
  
  process all cells in lexicographical order of their indices (row by row, from the left);
2. (b)
  
  for each cell, process all subcells within the cell in lexicographical order.

In our analysis, we make certain assumptions on the given $\delta$ with respect to the input curves, which can be ensured by applying a random small perturbation. We follow up our presentation of the decision algorithm with a justification for why this assumption does not lead to loss of generality in the context of using the decision algorithm in practice and to compute the Fréchet distance (Section 3).

2.2 Refining the free space diagram

We consider the boundary $B_{\delta}$ of $\mathrm{FSD}_{\delta}$ as a set of curves, as opposed to the boundary of a region. We define the three sets $E_{h},E_{v}$ and $I_{\text{sing}}$ of points on $B_{\delta}$ :

1.

The set $E_{h}\subset B_{\delta}$ of extrema of the free space in the $y$ direction (with horizontal tangent).
2.

The set $E_{v}\subset B_{\delta}$ of extrema of the free space in the $x$ direction (with vertical tangent).
3.

The set $I_{\text{sing}}$ of singularities of $B_{\delta}$ in the interior of the cells of $\mathrm{FSD}_{\delta}$ , consisting of points where $B_{\delta}$ is not $C^{1}$ , which includes points of self-intersection and cusps.

The geometry of $B_{\delta}$ is related to the geometry of equidistant curves and can be quite complicated in general. In Section 3, we show that for almost all $\delta$ , there are no singular points of $B_{\delta}$ in the interior of each cell in $\mathrm{FSD}_{\delta}$ associated to the smooth pieces of the curves, so that $I_{\text{sing}}=\emptyset$ , after possibly applying a small perturbation to $\delta$ . We note that for the norms $\ell_{1}$ and $\ell_{\infty}$ in the definition of the Fréchet distance, $B_{\delta}$ may contain cusp singularities for all values of $\delta$ in an open interval.

Using the points in $E_{h}$ , $E_{v}$ (and $I_{\text{sing}}$ ), we define a partition of each cell of the free space diagram $\mathrm{FSD}_{\delta}$ that lends itself to combinatorial investigations into the decision problem. For simplicity of exposition, we assume that each of $E_{h}$ , $E_{v}$ and $I_{\text{sing}}$ is a collection of isolated points. In particular, $B_{\delta}$ does not have a vertical or horizontal segment, which means that there is no arc of one curve that lies at a constant distance $\delta$ from a point on the other. If there are such circular arcs in any of the three sets, then in the following we represent each such arc by a single point lying on it, distinct from others in the sets.

For a point $z\in E_{h}$ ( $E_{v}$ ), we fix the cell in $\mathrm{FSD}_{\delta}$ containing $z$ , and trace the vertical (horizontal) line incident to $z$ inside this cell. For every point $z_{s}\in I_{\text{sing}}$ , similarly trace a horizontal line incident to $z_{s}$ . The result is a refinement of each cell of $\mathrm{FSD}_{\delta}$ into a collection of subcells $\{S\}$ . Figure 2 shows an illustration of the refinement inside a cell of $\mathrm{FSD}_{\delta}$ .

Lemma 2.1.

The boundary $B_{\delta}$ of the free space in the interior of each subcell in $\{S\}$ is a union of smooth arcs that are monotone in both coordinates of $\mathbb{R}^{2}$ and are disjoint except possibly at the boundary of a subcell.

Proof 2.2 (Proof of Lemma 2.1).

Consider a curve $\beta$ representing a connected component of $B_{\delta}$ inside the interior of a subcell $\mathcal{S}$ . Observe that $\beta$ cannot intersect another arc of $B_{\delta}$ in the interior of $\mathcal{S}$ and that $\beta$ is at least $C^{1}$ , as the singular points of $B_{\delta}$ are confined to the boundaries of the subcells in $\{S\}$ .

If $\beta$ is not monotone in either coordinate, consider the case that $\beta$ starts on the bottom edge of $\mathcal{S}$ and is not vertical and thus locally given as a function of $x$ . If $\beta$ is not monotone in the $x$ -coordinate, then there are $x_{1}\neq x_{2}$ such that $\frac{d\beta(x_{1})}{dx}=\beta^{\prime}(x_{1})>0>\beta^{\prime}(x_{2})$ . By continuity, there is a point $x^{*}\in(x_{1},x_{2})$ with $\beta^{\prime}(x^{*})=0$ , whence $x^{*}\in E_{h}$ . By construction, $x^{*}$ then lies on the vertical boundary of $\mathcal{S}$ . Other cases for $\beta$ can be treated similarly.

We record each intersection $\mathcal{I}_{\mathcal{S}}$ of $B_{\delta}$ with the boundary of each subcell $\mathcal{S}$ , which together form the set $\mathcal{I}=\bigcup_{\mathcal{S}\text{ is subcell}}\mathcal{I}_{\mathcal{S}}$ of all intersections of subcell walls with $B_{\delta}$ .

The construction of $\mathcal{I}$ consists of finding the intersections of a horizontal or vertical line in $\mathrm{FSD}_{\delta}$ with $B_{\delta}$ , which amounts to computing the intersections of a given smooth piece of $\gamma_{1}$ , with a sphere of radius $\delta$ centered at a point of $\gamma_{2}$ (and vice versa, switching the roles of $\gamma_{1}$ and $\gamma_{2}$ ). The associated values for $(x,y)$ in $\mathrm{FSD}_{\delta}$ correspond to the parameter values for the computed points on each curve.

In the following, we impose the general position assumption that $\delta$ is such that $I_{\text{sing}}=\emptyset$ and postpone a justification for this assumption to Section 3. The boundary $B_{\delta}$ can be naturally interpreted as a graph $G_{\delta}$ with vertex set $\mathcal{I}$ . Each edge of $G_{\delta}$ is a monotone arc contained in a subcell, by Lemma 2.1. In the remainder of this section we focus on elucidating two crucial observations regarding $G_{\delta}$ . The first is that the combinatorial structure of $G_{\delta}$ , i.e., which points of $\mathcal{I}_{\mathcal{S}}$ are connected by monotone edges in $B_{\delta}$ , can be deduced from the set $\mathcal{I}_{\mathcal{S}}$ along with what we call slope information at certain points, which is readily computable additional information which we introduce more carefully below. The second observation is that the answer to the decision problem does not depend on the monotone arcs joining points on subcell walls. In other words, the combinatorial structure of $G_{\delta}$ is sufficient to answer the decision problem, which justifies referring to $G_{\delta}$ as a combinatorial model for $\mathrm{FSD}_{\delta}$ . We elaborate on the necessary adjustments to the existing framework for the decision algorithm for polygonal curves in more detail in Subsection 2.3.

To begin with, we partition the two sets $E_{h}$ and $E_{v}$ into the sets $E_{h}^{+}$ and $E_{h}^{-}$ , and $E_{v}^{+}$ and $E_{v}^{-}$ , respectively, according to whether the forbidden region lies locally to the right of or above the point ( $-$ ), or to the left of or below the point ( $+$ ). For the bottom and left edge of each subcell $\mathcal{S}$ , we refer to the information of whether the boundary $B_{\delta}$ at each point in $\mathcal{I}_{\mathcal{S}}$ is increasing or decreasing as a function of the horizontal $x$ -coordinate as the slope information of these points. In other words, the slope information at a point $z\in\mathcal{I}_{\mathcal{S}}$ can be thought of an extra bit associated to $z$ that encodes whether $B_{\delta}$ curves to the left or to the right at $z$ . In Figure 2, the slope information is illustrated by an arrow pointing to the left or right (top or bottom) next to the point on the bottom (left) edge of $\mathcal{D}_{\delta}$ .

The following somewhat surprising statement is the main result of this section and shows that the slope information on the bottommost and leftmost edges of the original cells of $\mathrm{FSD}_{\delta}$ leads to a construction recipe for the combinatorial structure of $G_{\delta}$ .

Lemma 2.3.

Assume $\delta$ is such that $I_{\text{sing}}=\emptyset$ . There is an algorithm that reproduces the combinatorial structure of $G_{\delta}$ , using the sets $E_{h}^{+},E_{h}^{-},E_{v}^{+},E_{v}^{-}$ , and $\mathcal{I}$ along with the slope information on the bottommost and leftmost edges of $\mathrm{FSD}_{\delta}$ , in time $O(\lvert\mathcal{I}\rvert)$ .

Proof 2.4.

By Lemma 2.1, each subcell $\mathcal{S}$ contains only arcs that are monotone in both coordinates. We show that the slope information at the points in $\mathcal{I}_{\mathcal{S}}$ that lie on the lower and left edge of $\mathcal{S}$ is sufficient to know how they are connected through arcs in $B_{\delta}$ inside $\mathcal{S}$ . Transferring the slope information along arcs, we can thus find the structure of $G_{\delta}$ in all subcells incrementally, starting from the bottom left, where after every step there is a (new) subcell in $\{\mathcal{S}\}$ where the slope information is known on the bottom and left edges.

Assume first for simplicity that there are no points on the corners of $\mathcal{S}$ . We remove all points in $\mathcal{I}_{\mathcal{S}}$ (corresponding to points in $E_{v}$ or $E_{h}$ ) that only touch $\mathcal{S}$ , so that $B_{\delta}$ does not enter $\mathcal{S}$ . Each point $z\in\mathcal{I}_{\mathcal{S}}$ then has an incident arc that enters the interior of $\mathcal{S}$ , so every point in $\mathcal{I}_{\mathcal{S}}$ has to be paired with another such point. To find how they are matched, the algorithm proceeds incrementally, deducing at least one set of matching points at every step.

We consider a number of cases, depending on the behavior of $B_{\delta}$ at the as-of-yet unmatched points closest to the corners. Denote by $e_{b},e_{r},e_{t}$ and $e_{l}$ the bottom, right, top, and left edge of $\mathcal{S}$ . We further write $z_{l}^{b}$ and $z_{r}^{b}$ for the two unmatched points in $\mathcal{I}_{\mathcal{S}}$ on $e_{b}$ that are farthest apart, i.e., for the left-most and right-most unmatched points, respectively. We similarly define the points $z_{b}^{l},z_{t}^{l},z_{l}^{t},z_{r}^{t},z_{t}^{r}$ and $z_{b}^{r}$ on the edges $e_{l},e_{t},$ and $e_{r}$ , as illustrated in Figures 3 and 4. The combinations of the slope information at the points $z_{l}^{b},z_{r}^{b},z_{b}^{l}$ , and $z_{t}^{l}$ on the left and bottom edges yields a total of $2^{4}=16$ cases to consider, where we first assume that these 4 points are distinct. We will show how every case leads to a unique insertion of an arc of $B_{\delta}$ matching at least two vertices of $G_{\delta}$ , at which point we restart the process to insert another arc until every point is matched.

Case type 1

Consider the case where the arcs of $B_{\delta}$ at $z_{l}^{b}$ and $z_{r}^{b}$ move toward each other as in Figure 3(left). Then there is no arc in $B_{\delta}$ that connects any point on $e_{l}$ to $e_{r}$ and thus $z_{t}^{l}$ necessarily connects to $z_{l}^{t}$ . Since the same argument holds if the arcs of $B_{\delta}$ at $z_{t}^{l}$ and $z_{b}^{l}$ curve toward each other as in Figure 3(right), this resolves a total of $7$ different possibilities.

Case type 2

Let $B_{\delta}$ be decreasing at $z_{l}^{b}$ and at $z_{b}^{l}$ . Since each arc is monotone, $z_{l}^{b}$ cannot be joined to any point lying above $z_{b}^{l}$ , so these two points have to be matched. This takes care of $4$ further cases.

Consider next the case where $B_{\delta}$ is decreasing at $z_{l}^{b}$ . The case of $B_{\delta}$ decreasing at $z_{b}^{l}$ having already been treated above, assume otherwise, so that $z_{l}^{b}$ does not connect to a point on $e_{l}$ . Moreover, none of the points on $e_{l}$ can connect to points on $e_{r}$ or $e_{b}$ , so they have to be joined to points on $e_{t}$ . Therefore, if $k_{l}$ is the number of unmatched points on $e_{l}$ , $z_{l}^{b}$ connects to the $(k_{l}+1)$ -th point on $e_{t}$ (and the leftmost $k_{l}$ points on $e_{t}$ get joined to points on $e_{l}$ ). The case where $B_{\delta}$ decreases at $z_{b}^{l}$ is analogous, concluding a total of 15 cases.

Last case

The only remaining case not yet treated is the case where $B_{\delta}$ is increasing at each of the four points in question, as depicted in Figure 4(right). There are two possibilities. If $z_{t}^{l}$ is not joined by an arc to $z_{l}^{t}$ , then it must be joined to the $(k_{t}+1)$ -th point $z_{k_{t}+1}^{r}$ on $e_{r}$ (counted from the top), where $k_{t}$ is the number of unmatched points in $\mathcal{I}_{\mathcal{S}}$ on $e_{t}$ .

The two cases can be distinguished by a simple rule. Let $k_{b}$ and $k_{r}$ denote the number of unmatched points on $e_{b}$ and $e_{r}$ , respectively. If $z_{t}^{l}$ is connected to the $(k_{t}+1)$ -th point on $e_{r}$ , then all of the unmatched points in $\mathcal{I}_{\mathcal{S}}\cap e_{t}$ have to be connected to $e_{r}$ and no point on $e_{l}$ can be joined to $e_{t}$ . Since no point on $e_{l}$ connects to $e_{b}$ because of the slope, we find that

\displaystyle k_{l}+k_{b}+k_{t}=k_{r}.

(1)

Since every point has to be joined, (1) alone also implies that no point on $e_{l}$ can be joined to $e_{t}$ , distinguishing the two cases.

After having matched all points in $\mathcal{I}_{\mathcal{S}}$ , we can transfer the slope information from points on the bottom and left edges to the points on $e_{t}$ and $e_{r}$ . Note for this that the behavior does not change for points that are in neither of $E_{h}^{+},E_{h}^{-},E_{v}^{+},$ , or $E_{v}^{-}$ , for which the slope at the corresponding points is clear. Lastly, the remaining points on $e_{r}$ and $e_{t}$ without slope information that have been matched to each other are marked as decreasing.

To conclude the proof, we next deal with degenerate cases and corner points.

The degenerate cases

Consider now the cases where there are no four pairwise distinct points $z_{l}^{b},z_{r}^{b},z_{b}^{l}$ , and $z_{t}^{l}$ . Notice first that the above analysis already treats the case where there are only three distinct such unmatched points. Also, none of the above cases require the slope information for all four points, so the case study also applies in this situation.

The next case is that of only two distinct extremal points on $e_{b}\cup e_{l}$ , which again can be treated very similarly. Likewise, the case of a single point on $e_{b}\cup e_{l}$ can be settled in the same way. Last, consider the undiscussed situation where all points on $e_{b}$ and $e_{l}$ have been matched. In this case, the unmatched points on $e_{t}$ have to be matched with those of $e_{r}$ .

Corner points

To conclude the proof that the points in $\mathcal{I}_{\mathcal{S}}$ can be uniquely joined in $\mathcal{S}$ , we still need to discuss the case where there are points in $\mathcal{I}_{\mathcal{S}}$ on the corners of $\mathcal{S}$ . For corner points on $e_{b}$ or $e_{l}$ , the slope information tells us whether or not to include these points in $\mathcal{I}_{\mathcal{S}}$ for the matching process. To check if a point in the upper right hand corner $c_{tr}:=e_{t}\cap e_{r}$ needs to be considered in the absence of slope information for that corner point, we first observe that none of the points on $e_{t}$ or $e_{r}$ can connect to $c_{tr}$ . If $c_{tr}$ connects to some other point in $\mathcal{I}_{\mathcal{S}}$ , then no point on $e_{r}$ can connect to $e_{t}$ . Hence, we see that

\displaystyle k_{l}+k_{b}-2n_{bl}=k_{t}+k_{r},

(2)

where $n_{bl}$ denotes the number of points on $e_{b}$ that connect to a point on $e_{l}$ . The quantities $k_{l},k_{b},k_{t},k_{r}$ are defined as above, with the convention that the top left and bottom left corner only counts for $k_{l}$ , the bottom right corner for $k_{b}$ , and $c_{tr}$ for $k_{t}$ . Note that the points in any pair of matched points in $e_{l}\cup e_{b}$ are incident to a decreasing arc of $B_{\delta}$ . Therefore, none of them can connect to $c_{tr}$ . Furthermore, no such pair of points can be separated by an arc from $c_{tr}$ . Thus, (2) can only be valid for a specific value of $k_{t}$ .

In case $c_{tr}$ is not part of $\mathcal{I}_{\mathcal{S}}$ , let $n_{tr}\geq 0$ denote the number of points on $e_{t}$ that are connected to a point on $e_{r}$ . Then $k_{l}+k_{b}-2n_{bl}=(k_{t}-1)+k_{r}-2n_{tr}$ , and we see that the right hand side decreases with each pair of matched points from $e_{t}$ and $e_{r}$ . All in all, we see that to check if $c_{tr}$ belongs to $\mathcal{I}_{\mathcal{S}}$ , one calculates the left and right hand side of (2). Their difference determines if $c_{tr}$ belongs to $\mathcal{I}_{\mathcal{S}}$ .

Remark 2.5.

Figure 5 illustrates the necessity of some knowledge of the slope information on edges of a subcell for the accurate reconstruction of $B_{\delta}$ inside a cell.

Deriving the slope information

In the following, we explain how to derive the slope information for points in a subcell by evaluating the distance between the two curve segments at specific test points along their parametrization. The process is illustrated in Figure 6. We explain the approach using the example of an extremal point $z\in E_{h}$ , which belongs to either $E_{h}^{+}$ or $E_{h}^{-}$ , depending on the distance evaluated at three test points. The three points are any points lying, sufficiently close, below, above, and to the left (or right) of $z$ . Two of the three points either both belong to the free space or both to the forbidden region, and one will not, determining whether $z\in E_{h}^{+}$ or $z\in E_{h}^{-}$ , as illustrated in Figure 6. A similar analysis can be used to determine the slope information associated to other points $z\in I$ (as long as $z\not\in I_{\text{sing}}$ ).

Since $z$ lies on the (vertical) boundary of a cell, at least two of the points have natural candidates: We can choose any point on the boundary of the cells that is closer to $z$ than any other intersection point with $B_{\delta}$ lying on the same (vertical) line. To guarantee that the chosen point in the horizontal direction is sufficiently close to $z$ for the analysis to work, we use the same machinery as before in the construction of the cell decomposition. Denoting $z=(z_{x},z_{y})$ , let $z^{*}$ be the first number smaller than $z_{x}$ where $\gamma_{1}$ (parametrized by the horizontal axis) intersects the ball of radius $\delta$ centered at $\gamma_{2}(z_{y})$ . Then the point of evaluation is chosen from the open interval $(z^{*},z_{x})$ .

2.3 Monotone paths in the free space diagram and the decision problem

In this section, we use the machinery developed above to derive an algorithm that answers the decision problem.

Definition 2.6.

The reachable free space $\mathcal{R}_{\leq\delta}(\gamma_{1},\gamma_{2})$ of two curves $\gamma_{1}$ and $\gamma_{2}$ is the subset of all points of the free space $\mathcal{D}_{\delta}(\gamma_{1},\gamma_{2})$ that are reachable from the origin by a path monotone in both coordinates. The complexity $N_{\leq\delta}(\gamma_{1},\gamma_{2})$ of the reachable free space is the number of original cells with non-empty intersection with $\mathcal{R}_{\leq\delta}(\gamma_{1},\gamma_{2})$ .

As before, we can assume (by Proposition 3.12 below) that $\delta$ is such that there are no singularities on the boundary curves $B_{\delta}$ of the free space. We will later show (Proposition 3.14) that for algebraically bounded curves the decomposition of $\mathrm{FSD}_{\delta}$ and point set in Lemma 2.3 (corresponding to the vertices of the graph $G_{\delta}$ ) consists of $O(mn)$ elements (depending on the allowed degrees of the curves). To obtain bounds on the running time of the algorithm, in the following we assume that the investigated curves are algebraically bounded. A reachable interval $R$ is a maximal interval of points on a boundary edge of a subcell, such that every point in $R$ is reachable from the origin by a path contained in the free space, that is monotone in both coordinates. In particular, horizontal (vertical) reachable intervals always end on the right (top) either at a vertex of $G_{\delta}$ , or at a cell wall, so there are at most $O(mn)$ reachable intervals. Consider, for example, a reachable interval $R$ on the bottom edge of a cell and its left-most point $b_{l}$ . Points reachable from $b_{l}$ clearly include all points reachable from any point to the right of $b_{l}$ within the same interval of free space on the edge. By Lemma 2.1, there is at most one reachable interval on each of the top and right edges of a subcell $\mathcal{S}$ that is reachable by a monotone path starting from a reachable interval on the left (or bottom) edge of $\mathcal{S}$ , as illustrated in Figure 7. The set of reachable intervals on the top and right edges of $\mathcal{S}$ can be readily computed in constant time from the coordinates of the vertices of $G_{\delta}$ along with its combinatorial information.

We obtain a graph representation of the reachable intervals as follows. Every reachable interval corresponds to a vertex and two vertices are joined by an edge if both intervals belong to the same subcell and every point of one of the reachable intervals can be joined by a monotone path to some point on the other interval. To construct the resulting graph $\mathcal{R}$ , consider the original cell decomposition of $\mathrm{FSD}_{\delta}$ . We start by checking if $(0,0)\in\mathcal{D}_{\delta}$ and then iterate through the original cells from the bottom left in every row and subsequently move up row by row, computing the reachable intervals on the top and right boundary edges of each cell at every step. To compute these reachable intervals, we compute the reachable intervals on the constant number of subcells in each cell in the same fashion, processing a total of $O(N_{\leq\delta}(\gamma_{1},\gamma_{2}))$ cells. Observe that all reachable intervals have $x$ and $y$ coordinates that are each already present in the coordinates of the marked points, i.e., vertices of $G_{\delta}$ . (We can also compute the combinatorial structure of $G_{\delta}$ within a subcell while processing it, as described in the proof of Lemma 2.3.) All in all, we obtain the following result.

Proposition 2.7.

Given two algebraically bounded piecewise smooth curves $\gamma_{1}$ , $\gamma_{2}$ in $\mathbb{R}^{d}$ comprised of $m$ and $n$ pieces, respectively, and a value of $\delta$ such that $B_{\delta}$ has no singularities, one can decide if $\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2})\leq\delta$ . The running time is bounded by $O(mn)$ .

Remark 2.8.

In contrast to the situation for polygonal curves, our solution to the decision problem does not automatically yield a parametrization of $\gamma_{1}$ and $\gamma_{2}$ that realizes the given distance of $\delta$ . One way of obtaining such parametrizations would be through parametrizations of the arcs of $B_{\delta}$ .

We note that a necessary ingredient for the above decision algorithm is being able to compare the coordinates of the points in the set of points used in the construction of the partitioning of $\mathrm{FSD}_{\delta}$ . No further algebraic operations are required to solve the decision problem. Observe that the answer to the decision problem depends only on the combinatorial structure of $G_{\delta}$ and the ordering of the $x$ - and $y$ -coordinates of the marked points $\mathcal{I}$ that give rise to the partition. Away from critical values of $\delta$ , the answer therefore does not change when applying a sufficiently small perturbation of the marked points. Furthermore, in the following section, we deduce that the number of marked points for algebraically bounded curves is bounded, and also show that the number of values of $\delta$ for which the answer to the decision problem is subject to change is bounded for such curves. In particular, we observe that the decision algorithm does not crucially depend on evaluating the required algebraic operations exactly, but can also be carried out approximately.

3 The structure of the boundary $B_{\delta}$ of the free space

In this section, we complement the introduced computational approach with results concerning the structure of singular points on $B_{\delta}$ that guarantee that our algorithms work correctly. The material in this section provides the technical foundation for the approach outlined above. Observe that even for straight edges, in case of the $\ell_{1}$ or $\ell_{\infty}$ norm, $B_{\delta}$ can feature non-smooth points that persist when varying $\delta$ , as the free space is the intersection of a parallelogram with $[0,1]^{2}$ (refer to [1]). Although our framework can be adjusted to include these cases, for simplicity, we exclude the values $p=1$ and $p=\infty$ from our treatment. We discuss the different scenarios for all remaining $\ell_{p}$ norms, starting with general smooth curves and subsequently focusing on algebraically bounded curves; see [10] for background on algebraic curves and degree. The central property of an algebraic curve we use is that it cannot intersect a hyperplane in general position more than a constant number (depending on the allowed degree) of times.

Defining the function $f_{p,\gamma_{1},\gamma_{2}}:[0,1]^{2}\to\mathbb{R}$ by $f_{p,\gamma_{1},\gamma_{2}}(t_{1},t_{2})=\sum_{i}(|(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})|)^{p}$ , we have that $B_{\delta}=\{(t_{1},t_{2})|f_{p,\gamma_{1},\gamma_{2}}(t_{1},t_{2})=\delta^{p}\}\subset[0,1]^{2}$ . There are two possible types of singular points of $B_{\delta}$ — cusps and points of self-intersection — characterized as those points that do not have a well-defined tangent defined by the Jacobi matrix (gradient) $J:=Df_{p,\gamma_{1},\gamma_{2}}$ . The singular points correspond to critical points of the function $f_{p,\gamma_{1},\gamma_{2}}$ . The image of a critical point is known as a critical value. The entries $J_{k}(t_{1},t_{2})$ for $k=1,2$ are given by

\displaystyle J_{k}(t_{1},t_{2})=p\sum_{i}|(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})|^{p-2}((\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2}))(-1)^{k+1}(\gamma_{k})^{\prime}_{i}(t_{k}).

(3)

The singular points of $B_{\delta}$ can thus be described as

	$\displaystyle I_{\text{sing}}=\biggl{\{}(t_{1},t_{2})\bigg{\|}$	$\displaystyle\sum_{i}(\|(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})\|)^{p-2}((\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2}))(\gamma_{1})^{\prime}_{i}(t_{1})=0,$		(4)
	$\displaystyle-$	$\displaystyle\sum_{i}(\|(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})\|)^{p-2}((\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2}))(\gamma_{2})^{\prime}_{i}(t_{2})=0\biggr{\}}\cap B_{\delta}.$		(4)

Geometrically, critical points of $f_{p,\gamma_{1},\gamma_{2}}$ for $1<p<\infty$ can be described as pairs of points $(t_{1},t_{2})$ on $B_{\delta}$ satisfying the additional criteria

\displaystyle\frac{\mathrm{d}}{\mathrm{d}t_{1}}\|\gamma_{1}(t_{1})-\gamma_{2}(t_{2})\|_{p}=0=\frac{\mathrm{d}}{\mathrm{d}t_{2}}\|\gamma_{1}(t_{1})-\gamma_{2}(t_{2})\|_{p}.

(5)

Observe that both equations in (4) (or (5)) are continuous for $1<p<\infty$ . The implicit function theorem guarantees that, away from critical points, $B_{\delta}$ can be described as a collection of planar $C^{1}$ curves, as illustrated in Figure 8.

The intuitive idea behind the investigations of this section is that since the two equations in (4) are independent of $\delta$ , the solution set (the singular points) should ideally be a collection of isolated points, so that there are only isolated critical values of $\delta$ to which they belong.

Since both $\gamma_{1}$ and $\gamma_{2}$ are $C^{2}$ , the function $f_{p,\gamma_{1},\gamma_{2}}$ is $C^{2}$ for $2\leq p<\infty$ , and $C^{1}$ for $1<p<2$ (see also (6) below). For the sake of completeness, we derive the coefficients $H_{kl}(t_{1},t_{2})$ , with $k,l\in\{1,2\}$ , of the Hessian $H$ of $f_{p,\gamma_{1},\gamma_{2}}$ , from the Jacobian $J_{k}$ in (3) of $f_{p,\gamma_{1},\gamma_{2}}$ . Up to multiplication by a constant $C$ , we compute $H_{kl}$ by differentiating the equations (4), which yields

$\displaystyle C\cdot H_{kl}(t_{1},t_{2})=$	$\displaystyle\sum\limits_{i}\|(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})\|^{p-2}\biggl{(}(p-2)(-1)^{l+k}(\gamma_{l})^{\prime}_{i}(t_{l})(\gamma_{k})^{\prime}_{i}(t_{k})+$	(6)
	$\displaystyle(-1)^{l+k}(\gamma_{k})^{\prime}_{i}(t_{k})(\gamma_{l})^{\prime}_{i}(t_{l})+(-1)^{k+1}\delta_{kl}((\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2}))(\gamma_{k})^{\prime\prime}_{i}(t_{k})\biggr{)}$
$\displaystyle=$	$\displaystyle\sum\limits_{i}\|(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})\|^{p-2}\biggl{(}(-1)^{k+l}(p-1)(\gamma_{l})^{\prime}_{i}(t_{l})(\gamma_{k})^{\prime}_{i}(t_{k})$
	$\displaystyle+(-1)^{k+1}\delta_{kl}((\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2}))(\gamma_{k})^{\prime\prime}_{i}(t_{k})\biggr{)},$

where $\delta_{kl}$ is the Kronecker delta, which has the value one for $k=l$ and zero otherwise.

Example 3.1.

In case of the Euclidean norm, where $p=2$ , the singularities $(t_{1},t_{2})$ satisfy the orthogonality condition

\displaystyle\left<\gamma_{1}(t_{1})-\gamma_{2}(t_{2}),\gamma_{1}^{\prime}(t_{1})\right>=0=\left<\gamma_{1}(t_{1})-\gamma_{2}(t_{2}),\gamma_{2}^{\prime}(t_{2})\right>.

(7)

The singularities thus correspond to pairs of points, one on each of the curves, at which the two tangent vectors are contained in the hyperplane orthogonal to the vector between the pair of points.

Consider the two curves $\gamma_{1}(t)=(t,0)$ and $\gamma_{2}(t)=(t,t^{5}\sin(\frac{1}{t})+\alpha)$ for $t\neq 0$ and $\gamma_{2}(t)=(0,\alpha)$ , for some $\alpha\in\mathbb{R}$ . Notice that both $\gamma_{1}$ and $\gamma_{2}$ are $C^{2}$ curves. Since $(\gamma_{2})_{2}$ has infinitely many zeros in $[0,1]$ , its derivative also has infinitely many zeros in $[0,1]$ , so there are infinitely many critical points of $f_{p,\gamma_{1},\gamma_{2}}$ in $[0,1]$ for $p=2$ , giving rise to infinitely many critical values. Observe also that the related function $\gamma_{2}(t)=(t,\exp(-\frac{1}{t^{2}})\sin(\frac{1}{t})+\alpha)$ for $t\neq 0$ and $\gamma_{2}(0)=(0,\alpha)$ is infinitely differentiable in $[0,1]$ and has the same property.

Remark 3.2.

One might find it desirable to find assumptions which imply that the function $f_{p,\gamma_{1},\gamma_{2}}$ is a Morse function. A Morse function is a $C^{2}$ function where the Hessian is non-singular at critical points, see [9]. The Morse lemma would then imply that the critical points described by the equations (4) are isolated, so that the same is also true for the critical values. However, it is noteworthy that there are cases where a small rotation and translation of one of the curves is not be enough to ensure that the critical points are isolated, as can be seen by an adjustment of Example 3.1.

We have the following result regarding the regular, i.e., non-critical values of $f_{p,\gamma_{1},\gamma_{2}}$ . To simplify the exposition, we assume that $\gamma_{1}$ and $\gamma_{2}$ are smooth, so that $\mathrm{FSD}_{\delta}$ consists of a single cell. In particular, we can ignore singularities of $B_{\delta}$ due to the nonsmoothness of the curves where the smooth pieces join.

Proposition 3.3.

The set $\mathcal{R}$ of regular values of $f_{p,\gamma_{1},\gamma_{2}}$ is open in $\mathbb{R}$ for $1<p<\infty$ and dense if $2\leq p<\infty$ . For $1<p<2$ , there is a dense and open set in $\mathbb{R}$ in which the only possible singular points of $f_{p,\gamma_{1},\gamma_{2}}$ are the points $(t_{1},t_{2})$ where $(\gamma_{1})_{i}(t_{1})=(\gamma_{1})_{i}(t_{2})$ for some $1\leq i\leq d$ . If the points $(t_{1},t_{2})$ where $(\gamma_{1})_{i}^{\prime}(t_{1})=(\gamma_{2})_{i}^{\prime}(t_{2})=0$ for all $i$ form a null set, then $\mathcal{R}$ is also dense for $1<p<\infty$ .

Proof 3.4.

Let $\delta_{n}\xrightarrow{n\to\infty}\delta$ be a sequence of critical values with limit $\delta$ . For every $\delta_{n}$ , there is a singular point $(t_{1}^{n},t_{2}^{n})$ satisfying (4). Since $[0,1]^{2}$ is compact, we can assume that $(t_{1}^{n},t_{2}^{n})$ converges by passing over to a subsequence. The set of critical values is then closed by continuity of (4) and $f_{p,\gamma_{1},\gamma_{2}}$ in both $t_{1}$ and $t_{2}$ for $1<p<\infty$ .

For $2\leq p<\infty$ , $f_{p,\gamma_{1},\gamma_{2}}$ is $C^{2}$ , so by the classical Morse-Sard theorem [14] the set of those $\delta^{p}>0$ that are the image of singular points in $B_{\delta}$ has Lebesgue measure zero in $\mathbb{R}$ . As the complement of a zero-set for the Lebesgue measure, the set of regular values is dense.

We argue similarly for $1<p<2$ . The regularity of $f_{p,\gamma_{1},\gamma_{2}}$ is insufficient to obtain strong bounds on the size of the set of singular values, even with recent generalizations of the Morse-Sard theorem [8]. We thus restrict attention to points $(t_{1},t_{2})$ where $(\gamma_{1})_{i}(t_{1})\neq(\gamma_{1})_{i}(t_{2})$ for all $i$ , where the Jacobian (3) of $f_{p,\gamma_{1},\gamma_{2}}$ is locally Lipschitz, which implies that the set of singular values has measure zero, at least when restricted to these points [3, Theorem 1]. The critical points $(t_{1},t_{2})$ of the equation $(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})=0$ are given by $(\gamma_{1})^{\prime}_{i}(t_{1})=0=(\gamma_{2})^{\prime}_{i}(t_{2})$ . If these form a set of measure zero in $[0,1]^{2}$ for each $i$ , then the image of their union under the $C^{1}$ map $f_{p,\gamma_{1},\gamma_{2}}$ is a null set with respect to the Lebesgue measure.

Remark 3.5.

If the curves $(\gamma_{1})_{i}$ and $(\gamma_{2})_{i}$ are both Morse functions for all $i$ , which is almost always the case, then $(\gamma_{1})_{i}(t_{1})-(\gamma_{2})_{i}(t_{2})$ also defines a Morse function $[0,1]^{2}\to\mathbb{R}$ on the product space $[0,1]^{2}$ [2, Exercise 4], which implies, by the Morse lemma, that the critical points are isolated [12, Theorem 3.1.1]. Therefore, the last assumption in Proposition 3.3 ensuring that $\mathcal{R}$ is dense for $1<p<\infty$ is satisfied for almost all curves.

Proposition 3.3 does not rule out accumulation points of singular values for general smooth curves, even when $p=2$ , as illustrated in Example 3.1.

Lemma 3.6.

Let $1<p<\infty$ , $c$ be a simple component of $B_{\delta}$ , such that $[0,1]^{2}\setminus c$ has two components, each with non-empty interior. Let $R_{c}$ be a region in $[0,1]^{2}$ enclosed by $c$ . If $\overline{R_{c}}$ admits a neighborhood that has empty intersection with all other components $c^{\prime}\neq c$ of $B_{\delta}$ , then $c$ is everywhere differentiable, i.e., $B_{\delta}$ does not have any cusps.

Proof 3.7.

We sketch the proof, which can be seen as a consequence of the classification of the shape of the free space inside a cell of the free space diagram associated to two line segments [1, Lemma 3], as the intersection of a smooth ellipse with a rectangle. The statement there is only for the $\ell_{2}$ -norm, but can be naturally extended by noting that for $1<p<\infty$ , the boundary of the set of all points with norm $\leq\delta$ from a given point is $C^{1}$ , as follows from the regular value theorem since any $\delta>0$ is a regular value of the $\ell_{p}$ -norm.

The question of whether a point $(t_{1},t_{2})$ on $c$ corresponding to the two points $\gamma_{1}(t_{1})$ and $\gamma_{2}(t_{2})$ on the two curves with distance $\delta$ is a cusp is inherently a local one. By differentiability of the two curves, they are approximated locally by their tangents and within a sufficiently small neighborhoods of $t_{1}$ and $t_{2}$ , we can picture the curves as a result of a differentiable deformation of their tangents at these points. Such a deformation leads to a similar local deformation of the boundary of the free space. Indeed, the boundary of the free space for the linear tangents is $C^{1}$ for noncritical values of the distance parameter $\delta$ , which remains that way after a small local differentiable deformation of the linear tangents. We therefore have $C^{1}$ regularity of $c$ at $(t_{1},t_{2})$ .

As a consequence of Lemma 3.6, the critical values of $f_{p,\gamma_{1},\gamma_{2}}$ for $1<p<\infty$ coincide with the appearance of a new component, or the merging of components in the free space diagram.

We will show that if the piecewise smooth curves $\gamma_{1}$ and $\gamma_{2}$ consist of algebraically bounded curves, Proposition 3.3 can be strengthened. To this end, we need some preparation.

Lemma 3.8.

Let $\gamma$ be an algebraically bounded curve. Then $\gamma$ is tangent to only finitely many $\ell_{2}$ -spheres centered at the origin, given by $\{x\in\mathbb{R}^{d}\;\mid\;\|x\|_{2}=r\}$ for some $r\in\mathbb{R}_{+}$ , with bound depending only on the degree bound of the curve.

Proof 3.9.

First note that the statement of the lemma is well-known to be true if we replace $\ell_{2}$ -spheres by hyperplanes orthogonal to a coordinate axis. Indeed, an algebraic curve of a given degree only has finitely many extrema in a given coordinate direction (if it is not contained in such a plane), as the extrema correspond to algebraic sets themselves, obtained through partial derivatives of each of the defining equations of $\gamma$ . To derive the statement for $\ell_{2}$ -spheres, we make use of a variant of stereographic projection that considers all $\ell_{2}$ -spheres of positive radius at the same time. For a sphere $S^{d-1}_{R^{2}}$ , centered at the origin, with radius $R^{2}$ , we define the function (see Figure 9)

S^{d-1}_{R^{2}}\owns(x_{1},\ldots,x_{d})\mapsto\left(\frac{2R^{2}}{R^{2}-x_{d}}(x_{1},\ldots,x_{d-1}),-R^{2}\right),

with inverse

\mathbb{R}^{d}\owns(x_{1},\ldots,x_{d-1},-R^{2})\mapsto\left(\frac{4R^{4}}{\sum_{i=1}^{d-1}x_{i}^{2}+4R^{4}}(x_{1},\ldots,x_{d-1}),\left(1-2\frac{4R^{4}}{\sum_{i=1}^{d-1}x_{i}^{2}+4R^{4}}\right)R^{2}\right).

Outside of the points where $x_{1}=x_{2}=\ldots=x_{d-1}=0$ , we obtain a rational map $\Psi$ defined on all of $\mathbb{R}^{d}$ , mapping all $\ell_{2}$ -spheres centered at the origin to hyperplanes, with rational inverse. Therefore, if $\gamma$ was tangent to infinitely many spheres, the algebraic curve that is its image under $\Psi$ would be tangent to infinitely many hyperplanes. However, as pointed out above, the number of times this can happen is a finite number depending on the degree of the algebraic curve in question, concluding the proof.

Lemma 3.10.

Algebraically bounded curves can intersect an $\ell_{p}$ -sphere only a finite number of times, with bound depending only on the degree bound.

Proof 3.11.

Assume otherwise, so that there is a sphere $S_{p}$ that intersects a curve $\gamma$ some large number of times. Since $S_{p}$ is compact, there are arbitrarily many intersection points within a small neighborhood $U$ in $S_{p}$ . Consider the pencil of $\ell_{2}$ -spheres centered at a point in the middle of $U$ . One readily sees that the number of times $\gamma$ is tangent to some sphere in this pencil can be made arbitrarily large, which would contradict Lemma 3.8.

The underlying idea of the proof of Lemma 3.10 can be also used to show the following.

Proposition 3.12.

Let $\gamma_{1}$ and $\gamma_{2}$ be algebraically bounded curves. Then there are only finitely many (with bound depending only on the degree bound) critical values of $f_{p,\gamma_{1},\gamma_{2}}$ for $1<p<\infty$ .

It is instructive to first consider the important case that $p=2$ , and both $\gamma_{1}$ and $\gamma_{2}$ have (componentwise) parametrizations as polynomials or more generally rational functions. Observe that in this case the set of critical points of $f_{p,\gamma_{1}\gamma_{2}}$ is an algebraic set, and thus the finite union of irreducible algebraic sets, which correspond to connected components in both the Zariski and the usual topology [10] (for this, instead of just real numbers, we also allow complex numbers as input for $f_{p,\gamma_{1},\gamma_{2}}$ ). The image on each connected set of critical points under the $C^{1}$ function $f_{p,\gamma_{1},\gamma_{2}}$ is constant, so the image of all critical points leads to only finitely many critical values of $f_{p,\gamma_{1},\gamma_{2}}$ . Note that the number of irreducible algebraic sets is bounded in terms of the degree bound of the curves.

Proof 3.13 (Proof of Proposition 3.12).

We now treat the general case, for which we argue geometrically. By Lemma 3.6, for $1<p<\infty$ , a critical value $\delta$ of the function corresponds to either the appearance of a new component of $B_{\delta}$ , or to two (or more) components becoming tangent, at some critical point $(x,y)\in[0,1]^{2}$ . In $\mathbb{R}^{d}$ , by (5), these events correspond to $\gamma_{1}$ becoming tangent at $\gamma_{1}(x)$ to an $\ell_{p}$ -ball centered at a point $\gamma_{2}(y)$ ; conversely, the same ball centered at $\gamma_{1}(x)$ is tangent to $\gamma_{2}$ at $\gamma_{2}(y)$ .

Assume that there are infinitely many distinct critical values $\delta$ where these events take place. Then, by compactness of $[0,1]^{2}$ , there is a convergent subsequence of critical points in $[0,1]^{2}$ corresponding to pairs of points on the two curves where these events happen for distinct values of $\delta$ . We can assume that the terms of the sequence are pairwise distinct. We consider the sequences as given by $(x_{k})_{k\in\mathbb{N}}$ and $(y_{k})_{k\in\mathbb{N}}$ in the first and second coordinates, respectively, and assume, without loss of generality, that the $y_{k}$ are pairwise distinct. The tangent vectors of $\gamma_{1}$ at $\{x_{k}\}$ lie in the hyperplanes tangent to balls centered at the convergent sequence of points $\gamma_{2}(y_{k})$ . For sufficiently large $k$ , the tangent vectors of $\gamma_{1}$ at $\gamma_{1}(x_{k})$ are roughly the same. As a consequence, the pencil of $\ell_{2}$ -spheres based at a point $z$ sufficiently close to $\gamma_{1}(x_{k})$ contains an unbounded number of tangencies to the curve $\gamma_{2}$ as $\gamma_{2}$ alternates between moving away from and towards $z$ . This is illustrated in Figure 10, showing the tangent vectors of $\gamma_{2}$ ‘bundle’ together around the eventual limit vector. We can further assume that the $\ell_{2}$ spheres do not contain an entire part of $\gamma_{2}$ by applying a small perturbation to the sphere if necessary. However, this would again contradict Lemma 3.8, so we can discard the assumption of infinitely many critical values of $f_{p,\gamma_{1},\gamma_{2}}$ .

To see that the number of critical values is in fact bounded by a constant depending on the bound on the degrees of the algebraic curves, we assume otherwise and argue very similarly to above. Indeed, given a sequence of curves with unbounded number of critical values leads to an arbitrary number of critical points within an arbitrary small neighborhood in $[0,1]^{2}$ . By rescaling, we can assume that the arclength of the curves in the sequence is bounded and thus, just as above, we have that an arbitrary number of critical points correspond to points and tangents on each of the curves that are arbitrarily close to each other.

Similarly to the proof of Proposition 3.12 which bounds the number of critical values of $\delta$ , we also obtain a similar bound on the number of marked points for a regular value of $\delta$ .

Proposition 3.14.

The number of points (components) in each of the sets $E_{h}^{+},E_{h}^{-},E_{v}^{+},E_{v}^{-}$ , (and $\mathcal{I}$ ) is at most a constant in each cell, for a total of $O(mn)$ , whenever $\gamma_{1},\gamma_{2}$ are algebraically bounded, consisting of $m$ , resp. $n$ smooth pieces, and $\delta$ is a regular value. The resulting decomposition of the free space diagram consists of $O(mn)$ cells.

Proposition 3.14 implies that the bound on the degree of a set of algebraically bounded curves determines a bound on the number of points used in the decomposition of $\mathrm{FSD}_{\delta}$ , for any regular value of $\delta$ , thereby providing the justification for the complexity bounds on the running-time of our decision algorithm. The proof is very similar to that of Proposition 3.12.

Proof 3.15 (Proof of Proposition 3.14).

Assume that there is a sequence of values for a given $\delta$ for which the number of points in, say, $E_{h}$ becomes greater than any given constant, then we can arrive at a contradiction, similarly to the proof of Proposition 3.12. The idea is that in this case, there has to be an arbitrary number of points in, say, $E_{h}$ , that are arbitrarily close to each other in $[0,1]^{2}$ . By rescaling the curves (and $\delta$ ) to normalize the length of the longer curve, we can assume that these points correspond to arbitrarily close points along $\gamma_{1}$ and in $\mathbb{R}^{d}$ . This again allows the construction of a pencil of $\ell_{2}$ -spheres with an arbitrary number of tangencies to $\gamma_{2}$ , contradicting Lemma 3.8.

By Lemma 3.10, we see that each of the finitely many extrema leads to only finitely many marked points. Again by rescaling, one can eliminate the possibility that the maximum number of points in $\mathcal{I}$ depends on $\delta$ .

4 The minimization problem of computing the Fréchet distance

The aim of this section is to use the solution of the decision problem to solve the optimization problem of finding the minimal $\delta$ for which the decision problem for two curves has a positive answer, which corresponds to the Fréchet distance between the curves. Assuming that all $m$ , resp. $n$ smooth pieces of $\gamma_{1}$ , resp. $\gamma_{2}$ are algebraically bounded curves, we show that the number of operations required for the computation is of the same complexity as the polygonal case. The results outlined in this section mostly essentially mirror those for smooth planar curves under the $\ell_{2}$ -distance in [13].

The central idea is to invoke Megiddo’s parametric search technique [11], together with the optimization introduced by Cole [6]. Parametric search is the standard approach to computing the Fréchet distance and its variants [1, 15, 13, 5]. In the following, we explain the adjustments necessary to apply it to the situation of algebraically bounded curves.

The combinatorial structure of the partition of the free space diagram introduced in Section 2 changes only at certain critical values of $\delta$ . In addition to these values being critical values of the function $f_{p,\gamma_{1},\gamma_{2}}$ introduced in Section 3, there are further possibilities. By Lemma 3.6, the only values of $\delta$ where the decision problem can change are related to the emergence or merging of components of free space, a component becoming tangent to the boundary of walls of original cells, a marked point appearing or disappearing, or the ordering of the $x$ - and $y$ -coordinates of the marked points changing. The results of the previous section imply that the set of $\delta$ where none of these events occur is open. Moreover, we observe that a new marked point that is not naturally related to a previously marked point can appear (or disappear) only a finite number of times, bounded by a constant depending on the degree of the algebraically bounded curves. Similarly to the proof of Proposition 3.14, this is again a consequence of the fact that if there did exist a sequence of values of $\delta$ with an ever increasing number of such events, then there is a sequence of points on the curves that ultimately contradict the property that algebraically bounded curves cannot be tangent to sphere centered at a fixed point more than a fixed number of times. A similar argument also shows that the ordering of the marked points cannot change more often than a constant depending on the degree bound of the curves, as the ordering is subject to change only when extremal points meet on the same vertical or horizontal line in $\mathrm{FSD}_{\delta}$ .

There are $O(mn)$ critical values of $\delta$ between which no marked points appear or disappear, and no components merge, appear, or start touching the boundary of cells. We apply a binary search among these $O(mn)$ critical values so that the only changes to the answer of the decision problem are due to a change of the order of the extremal points in the $x$ - and $y$ -direction. Every step of the binary search involves running the decision algorithm, resulting in a running time of $O(mn\log(mn))$ for this step. Note that since we cannot run our decision algorithm directly on these critical values, we have to move to a value for $\delta$ that lies between them. As a result, the binary search only narrows down the interval of $\delta$ to two possible, adjacent intervals, instead of one. Inbetween these $O(mn)$ critical values, we use Cole’s variant of parametric search with a parallel sorting algorithm for both the $x$ - and $y$ -coordinates of the marked points of $B_{\delta}$ , to obtain an overall running time of $O(mn\log(mn))$ . The value of the Fréchet distance $\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2})$ is the lowest point of the lowest interval in which the decision problem has a positive answer. The result is summarized in Theorem 4.1.

Theorem 4.1.

Let $\gamma_{1}$ and $\gamma_{2}$ be two algebraically bounded curves in $\mathbb{R}^{d}$ consisting of $m$ and $n$ pieces, respectively. Then the Fréchet distance between $\gamma_{1}$ and $\gamma_{2}$ can be computed in $O(mn)$ space and in $O(mn\log(mn))$ operations (of bounded algebraic complexity).

5 Simplification of piecewise smooth curves

In this section, we introduce an algorithm to simplify a piecewise smooth curve consisting of $n$ smooth pieces and runs in $O(n)$ time. We adapt the approach of [7] to our setting of piecewise smooth curves with appropriate changes.

Computing the simplification $\operatorname{simp}(\gamma)$ of a piecewise smooth curve $\gamma$ with respect to $\mu\in\mathbb{R}$ .

Starting with the first smooth piece $\gamma_{1}$ of $\gamma$ , consider its arc length $l(\gamma_{1})$ . If $l(\gamma_{1})\geq\mu$ , then we move on to the next piece $\gamma_{2}$ and start over from there. Let $\gamma_{i}:[0,1]\to\mathbb{R}^{d}$ be the first piece with $l(\gamma_{i})<\mu$ . Then $\gamma_{i}$ is contained in the ball $B(\gamma_{i}(0),\mu)$ of radius $\mu$ centered at $\gamma_{i}(0)$ . Following the curve $\gamma$ , let $\gamma_{j}$ be the first piece of $\gamma$ that leaves $B(\gamma_{i}(0),\mu)$ . We take the first point $p_{j}$ on $\gamma_{j}$ lying on the boundary $B(\gamma_{i}(0),\mu)$ and join $\gamma_{i}(0)$ to $p_{j}$ with a straight line of length $\mu$ , replacing the part of $\gamma$ between $\gamma_{i}(0)$ and $p_{j}$ ; and $\gamma_{j}$ with the part of it after $p_{j}$ . We then restart the procedure at $p_{j}$ . If after any piece $\gamma_{k}:[0,1]\to\mathbb{R}^{d}$ with $l(\gamma_{k})<\mu$ , $\gamma$ does not intersect the boundary of $B(\gamma_{k}(0),\mu)$ , then we remove the part of $\gamma$ after $\gamma_{k}(0)$ .

The simplification algorithm results in a piecewise smooth curve with each piece of having an arc length of at least $\mu$ . Note that the algebraic operation of intersecting $\gamma$ with a ball is the same operation required in the computation of the Fréchet distance between two curves.

Lemma 5.1.

The simplification $\gamma^{\prime}=\operatorname{simp}(\gamma,\mu)$ of a piecewise smooth curve defined by Algorithm 5 above satisfies $\gamma\subset\gamma^{\prime}\bigoplus B(0,\mu)$ . In particular, $\delta_{F}(\gamma^{\prime},\gamma)\leq\mu$ .

Here, $A\bigoplus B$ denotes the Minkowski sum of $A$ and $B$ . The situation is illustrated in Figure 11.

Proof 5.2.

Let $s^{\prime}$ be the first new segment of $\gamma^{\prime}$ and $s$ the portion of $\gamma$ that gets replaced by $s^{\prime}$ in $\gamma^{\prime}$ and has the same endpoints $p_{1}$ and $p_{2}$ as $s^{\prime}$ . Now, $s$ is contained in $B(p_{1},\mu)$ , so $s\subset s^{\prime}\bigoplus B(0,\mu)$ and the statement about the Minkowski sum follows, which in turn implies the statement about the Fréchet distance. Indeed, we can traverse $\gamma^{\prime}$ and $\gamma$ until $p_{1}$ , then traverse $\gamma\cap B(p_{1},\mu)$ while the parametrization of $\gamma^{\prime}$ stays on $p_{1}$ . Then, $s^{\prime}$ is traversed until $p_{2}$ is reached for both parametrizations, while maintaining a distance of at most $\mu$ .

5.1 Preserving $c$ -packedness

We make precise the idea that since each piece of a simplified curve $\operatorname{simp}(\gamma,\mu)$ is $\mu$ -close to $\gamma$ , the length contained in any ball cannot increase too much through the simplification.

Lemma 5.3.

Let $\gamma^{\prime}=\operatorname{simp}(\gamma,\mu)$ , with $\gamma$ a piecewise smooth curve. Then for any $p\in\mathbb{R}^{d}$ and $r\in\mathbb{R}$ , $l(\gamma\cap B(p,r+\mu))\geq l(\gamma^{\prime}\cap B(p,r))$ .

The situation is illustrated in Figure 12.

Proof 5.4.

Let $s^{\prime}$ be a segment of $\gamma^{\prime}$ and $s^{\prime}_{B}:=s^{\prime}\cap B(p,r)$ . Consider the subcurve $s$ of $\gamma$ that gets replaced by $s^{\prime}$ in $\gamma^{\prime}$ and has the same endpoints as $s^{\prime}$ . By Lemma 5.1, $s\subset s^{\prime}\bigoplus B(0,\mu)$ . Moreover, $s^{\prime}_{B}\bigoplus B(0,\mu)\subset B(p,r+\mu)$ , so $s\cap\left(s^{\prime}_{B}\bigoplus B(0,\mu)\right)\subset B(p,r+\mu)$ . Since $s^{\prime}_{B}$ is a straight line, it is the shortest path connecting its two endpoints. Therefore, we can erect two planes orthogonal to $s^{\prime}_{B}$ at the endpoints such that any path connecting these two planes must have length at least $l(s^{\prime}_{B})$ . In particular, since $s\cap s^{\prime}_{B}\bigoplus B(0,\mu)$ contains such a path, $l(s\cap\left(s^{\prime}_{B}\bigoplus B(0,\mu)\right))\geq l(s^{\prime}_{B})$ . The statement of the lemma follows by summing over the intersections of all pieces of $\gamma^{\prime}$ with $B(p,r)$ .

Lemma 5.5.

Let $\gamma$ be a $c$ -packed planar smooth curve and $\mu>0$ . Then the simplified curve $\gamma^{\prime}=\operatorname{simp}(\gamma,\mu)$ is a $7c$ -packed curve.

Proof 5.6.

For the sake of contradiction, assume that $l(\gamma^{\prime}\cap B(p,r))>7cr$ . We consider first the case that $r\geq\mu$ . Then Lemma 5.3 implies that $l(\gamma\cap B(p,r+\mu))\geq l(\gamma\cap B(p,r+\mu))\geq l(\gamma^{\prime}\cap B(p,\mu))>7cr$ . However, since $\gamma$ is $c$ -packed, we also have $l(\gamma\cap B(p,r+\mu))\leq(r+\mu)c\leq 2cr$ , a contradiction.

Let $r<\mu$ . Let $k$ denote the number of curve pieces of $\gamma^{\prime}$ in $B(p,r)$ and consider $k=k_{n}+k_{o}$ , where $k_{o}$ denotes the number of original pieces of $\gamma^{\prime}$ in $B(p,r)$ that are also present in $\gamma\cap B(p,r)$ and $k_{n}$ denotes the number of new curve pieces that intersect $B(p,r)$ . Since $\gamma$ is $c$ -packed, the curved pieces in $B(p,r)$ present in both $\gamma$ and $\gamma^{\prime}$ cannot have a total length greater than $cr$ . Therefore, if $l(\gamma^{\prime}\cap B(p,r))>7cr$ , then the new pieces have to add up in length to at least $6cr$ . Since the new pieces are straight lines they can contribute at most $2r$ in length to the intersection $\gamma^{\prime}\cap B(p,r)$ , so $k_{n}>6cr/2r=3c$ .

Observe that $l(\gamma^{\prime}\cap B(p,2\mu))\geq l(\gamma^{\prime}\cap B(p,r+\mu))\geq k_{n}\mu$ , since a new segment of $\gamma^{\prime}$ intersecting $B(p,r)$ also intersects $B(p,r+\mu)$ and each curve piece in $\gamma^{\prime}$ has length at least $\mu$ . Therefore, by Lemma 5.3, $l(\gamma\cap B(p,3\mu))\geq l(\gamma^{\prime}\cap B(p,2\mu))\geq l(\gamma^{\prime}\cap B(p,r+\mu))\geq k_{n}\mu>3c\mu$ , which contradicts the $c$ -packedness of $\gamma$ .

We note that the results and proofs in this section are valid for all simplifications of $c$ -packed curves, as long as the simplified curve

1.

is contained in a tubular neighborhood of the original curve,
2.

consists of pieces with arc length bounded from below by $\mu$ .

6 The relative free space complexity of simplified smooth curves

The central idea of the approximation algorithm for the decision problem for piecewise smooth curves is to replace the two curves in question with their simplifications. To study the complexity of the reachable free space, we examine the following central quantity.

Definition 6.1.

The $\epsilon$ -relative free space complexity of two curves $\gamma_{1}$ and $\gamma_{2}$ is

\displaystyle N(\epsilon,\gamma_{1},\gamma_{2})=\max\limits_{\delta\geq 0}N_{\leq\delta}(\operatorname{simp}(\gamma_{1},\epsilon\delta),\operatorname{simp}(\gamma_{2},\epsilon\delta)).

Proposition 6.2.

Let $\gamma_{1}$ and $\gamma_{2}$ be two piecewise smooth curves that are $c$ -packed and such that the arc length of each of the $n$ pieces is at least $\mu=\epsilon\delta$ . Then the number of cells in $\mathrm{FSD}_{\delta}(\gamma_{1},\gamma_{2})$ containing non-empty free space is in $O(cn/\epsilon)$ .

Proof 6.3.

Assign a counter to all pieces of the two curves, starting with the value $0$ . Each cell in $\mathcal{D}_{\leq\delta}(\gamma_{1},\gamma_{2})$ has two associated smooth pieces $u_{1}$ and $u_{2}$ of $\gamma_{1}$ and $\gamma_{2}$ , respectively. The free space in the cell associated to $u_{1}$ and $u_{2}$ is non-empty if and only if there are two points $p_{1}\in u_{1}$ and $p_{2}\in u_{2}$ such that $\|p_{1}-p_{2}\|\leq\delta$ . For every cell in $\mathcal{D}_{\leq\delta}$ with non-empty free space, we add one to the counter of the shorter of the two pieces. Figure 13 shows the pieces that contribute to the counter for $u_{1}$ in red. We bound the maximal possible value of the counter of each piece as follows.

For a piece $u$ of $\gamma_{1}$ , consider the ball $B(p_{m},(3/2)l(u)+\delta)$ of radius $(3/2)l(u)+\delta$ centered at its midpoint $p_{m}$ . By construction, the distance of every point of $u$ to the boundary of $B(p_{m},(3/2)l(u)+\delta)$ is at least $l(u)+\delta$ . Therefore, every piece of $\gamma_{2}$ that adds one to the counter of $u$ has an arc length of at least $l(u)$ in $B(p_{m},(3/2)l(u)+\delta)$ . Since $\gamma_{2}$ is $c$ -packed and $l(u)\geq\mu$ , the number of times we add one to the counter of $u$ is bounded from above by

	$\displaystyle c^{\prime}$	$\displaystyle=\frac{l(\gamma_{2})\cap B(p_{m},(3/2)l(u)+\delta)}{l(u)}\leq\frac{cr}{l(u)}=\frac{c(3/2l(u)+\delta)}{l(u)}=\frac{3}{2}c+\frac{\delta c}{l(u)}$
		$\displaystyle\leq\frac{3}{2}c+\frac{\delta c}{\mu}=O\left(\frac{c}{\epsilon}\right).$

Thus, there are at most $O(cn/\epsilon)$ cells containing free space, concluding the proof of the proposition.

Theorem 6.4.

Let $\gamma_{1}$ and $\gamma_{2}$ be two $c$ -packed piecewise smooth curves and $0<\epsilon<1$ . Then $N(\epsilon,\gamma_{1},\gamma_{2})=O(cn/\epsilon)$ .

Proof 6.5.

The simplification of a curve with parameter $\mu=\delta\epsilon$ consists of pieces with arc length at least $\mu$ . By Lemma 5.5, the simplifications are moreover $7c$ -packed. The claim thus follows from Proposition 6.2.

We can now apply the solution to the decision problem from Proposition 2.7 to the decision problem for the simplified curves. Using this decision procedure in place of that for polygonal curves, the otherwise same algorithms (Lemmas 3.5 and 3.6) in [7] can be used in our context to obtain an approximate solution to the decision problem for piecewise smooth $c$ -packed curves that runs in $O(N(\epsilon,\gamma_{1},\gamma_{2}))$ time. We note that $c$ -packedness is used only in its role in guaranteeing that $N(\epsilon,\gamma_{1},\gamma_{2})=O(cn/\epsilon)$ by Theorem 6.4.

Corollary 6.6.

Let $\gamma_{1}$ and $\gamma_{2}$ be two piecewise smooth algebraically bounded $c$ -packed curves, $1\geq\epsilon>0$ and $\delta>0$ . There is an algorithm that correctly outputs, in $O(cn/\epsilon)$ time, one of the following:

(i)

a $(1+\epsilon)$ -approximation to $\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2})$ ,
(ii)

$\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2})<\delta$ ,
(iii)

$\mathrm{d}_{\mathcal{F}}(\gamma_{1},\gamma_{2})>\delta$ .

References

[1] Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry and Applications, 05(01n02):75–91, mar 1995. doi:10.1142/S0218195995000064.
[2] Michèle Audin and Mihai Damian. Morse Theory and Floer Homology. Universitext. Springer London, London, 2014. URL: http://link.springer.com/10.1007/978-1-4471-5496-9, doi:10.1007/978-1-4471-5496-9.
[3] Sean Michael Bates. Toward a Precise Smoothness Hypothesis in Sard’s Theorem. Proceedings of the American Mathematical Society, 117(1):279, 1993. doi:10.2307/2159728.
[4] Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 661–670, 2014. arXiv:1404.1448, doi:10.1109/FOCS.2014.76.
[5] Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and Shripad Thite. Homotopic fréchet distance between curves or, walking your dog in the woods in polynomial time. Comput. Geom., 43(3):295–311, 2010. URL: https://doi.org/10.1016/j.comgeo.2009.02.008, doi:10.1016/J.COMGEO.2009.02.008.
[6] Richard Cole. Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM, 34(1):200–208, jan 1987. doi:10.1145/7531.7537.
[7] Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discrete and Computational Geometry, 48(1):94–127, 2012. arXiv:1003.0460, doi:10.1007/s00454-012-9402-z.
[8] Adele Ferone, Mikhail V. Korobkov, and Alba Roviello. On some universal Morse–Sard type theorems. Journal des Mathematiques Pures et Appliquees, 139:1–34, 2020. doi:10.1016/j.matpur.2020.05.002.
[9] Victor Guillemin and Alan Pollack. Differential Topology, volume 4. American Mathematical Society, Providence, Rhode Island, aug 2010. URL: http://www.ams.org/chel/370, doi:10.1090/chel/370.
[10] Robin Hartshorne. Algebraic Geometry, volume 52 of Graduate Texts in Mathematics. Springer New York, New York, NY, 1977. doi:10.1007/978-1-4757-3849-0.
[11] Nimrod Megiddo. Applying Parallel Computation Algorithms in the Design of Serial Algorithms. Journal of the ACM, 30(4):852–865, oct 1983. doi:10.1145/2157.322410.
[12] Louis Nirenberg. Topics in Nonlinear Functional Analysis, volume 6 of Courant Lecture Notes. American Mathematical Society, Providence, Rhode Island, apr 2001. doi:10.1090/cln/006.
[13] Günter Rote. Computing the Fréchet distance between piecewise smooth curves. Computational Geometry: Theory and Applications, 37(3 SPEC. ISS.):162–174, aug 2007. doi:10.1016/J.COMGEO.2005.01.004.
[14] Arthur Sard. The measure of the critical values of differentiable maps. Bulletin of the American Mathematical Society, 48(12):883–890, 1942. doi:10.1090/S0002-9904-1942-07811-6.
[15] René van Oostrum and Remco C. Veltkamp. Parametric search made practical. Comput. Geom., 28(2-3):75–88, 2004. URL: https://doi.org/10.1016/j.comgeo.2004.03.006, doi:10.1016/J.COMGEO.2004.03.006.