Faster Fréchet Distance Under Transformations

Many applications require determining the similarity of two geometric shapes, disregarding their location or orientation. More specifically, shape matching asks for the distance between two shapes if we allow the shapes to be transformed to minimize their distance [1, 3, 55]. Transformations may include translations, rotations, scaling, or a combination thereof. In this paper, we focus on polygonal curves under the Fréchet distance. Curves occur in many applications and need to be matched whenever they describe a local pattern, for example to recognize handwritten characters [49], trademarks [5], or movement patterns [17, 41, 44]. The Fréchet distance is arguably the most popular distance measure for curves in computational geometry. There has been significant algorithmic progress on the Fréchet distance, for instance, most recently on approximation [31, 52, 53], data structures [6, 12, 18, 27, 37, 38, 43, 42], algorithm engineering [8, 19, 34, 15, 13], simplification [11, 28, 51, 54], clustering [16, 20, 26, 44, 48, 21], Fréchet variants [22, 23, 24, 33, 36, 39, 40], and its complexity in general [10, 25, 30, 29].

The Fréchet distance under translation is defined as the minimum Fréchet distance for any translation of the curves. Computing the Fréchet distance under translations was first studied by Efrat, Indyk and Venkatasubramanian [35] and by Alt, Knauer and Wenk [4, 47, 56]. For two curves of total complexity $n$ in ${ℝ}^2$, an $\widetilde{𝒪}(n^{10})$ time algorithm¹¹1By $\widetilde{𝒪}(\cdot )$ we hide (poly-)logarithmic factors in $n$. for the Fréchet distance under translation was presented in [35], and an $\widetilde{𝒪}(n^8)$ time algorithm was presented in [4]. Wenk [56] generalized the approach in [4] to higher dimensions and a wide range of other transformations, e.g., for rotations or scalings in 2D in $\widetilde{𝒪}(n^5)$ time, or for affine transformations in $d$ dimensions in $\widetilde{𝒪}(n^{3(d^2+d)+2})$ time.

Despite significant algorithmic progress on various aspects of the Fréchet distance, no faster algorithms for computing the (continuous) Fréchet distance under transformations have been developed until now. In contrast, for computing the discrete Fréchet distance under translation, first an $\widetilde{𝒪}(n^6)$-time algorithm [45] was developed, then an $\widetilde{𝒪}(n^5)$-time algorithm [7], and more recently, an $\widetilde{𝒪}(n^{4+\frac{2}{3}})$-time algorithm [14].

A $d$-dimensional polygonal curve $\pi$ is a piecewise linear curve represented as a continuous mapping from $[1,n]$ to ${ℝ}^d$. For integer $i$, ${\pi }_i=\pi [i]$ is a vertex, and $\overline{{\pi }_i}={\pi }_i{\pi }_{i+1}=\pi [i,i+1]$ is a segment.

The Fréchet distance is a popular measure of the similarity between two polygonal curves. An orientation-preserving reparameterization is a continuous and bijective function $f:[0,1]\to [0,1]$ such that $f(0)=0$, and $f(1)=1$. The $0p{t}_{f,g}(\pi ,\sigma )$ between two curves $\pi$ and $\sigma$ with respect to the reparameterizations $f$ and $g$, is defined as follows.

Imagine the scenario where a person is walking their dog with a leash connecting them: the person needs to stay on $\pi$ while walking according to $f$, and the dog needs to stay on $\sigma$ while walking according to $g$. The maximum leash length is the width between $\pi$ and $\sigma$ with respect to the reparameterizations $f$ and $g$. The Fréchet distance $d_{ℱ}(\pi ,\sigma )$ is the minimum leash length required over all possible walks (defined by reparameterizations $f$ and $g$).

Problems relating to the Fréchet distance are commonly solved in a configuration space called the free-space diagram. In our problem, we assume for simplicity that both input curves have exactly $n$ vertices. The free-space ${ℱ}_{\delta }(\pi ,\sigma )$ is a collection of points in ${ℝ}^2$ in the range $[1,n]\times [1,n]$. A point $(x,y)$ is in the free-space if the Euclidean norm (distance) $\parallel \pi (x)-\sigma (y)\parallel$ between $\pi (x)$ and $\sigma (y)$ is at most $\delta$. As opposed to the free-space, we will call $[1,n]\times [1,n]\setminus {ℱ}_{\delta }(\pi ,\sigma )$ the forbidden space.

The free-space diagram $𝒟={𝒟}_{\delta }(\pi ,\sigma )$ is the partition of the free-space into $n\times n$ cells. A cell $C_{i,j}$ in $𝒟$ contains the free-space in the range $[i,i+1]\times [j,j+1]$. Alt and Godau [2] made the critical observation that the free-space within a cell $C_{i,j}$ is an intersection between an ellipse $E_{i,j}$ and the square $S_{i,j}=[i,i+1]\times [j,j+1]$; hence it is convex with constant description complexity. They also showed that $d_{ℱ}(\pi ,\sigma )\le \delta$ if and only if there is a bi-monotone path in ${𝒟}_{\delta }(\pi ,\sigma )$ from $(1,1)$ to $(n,n)$ through the free-space.

An intersection between the boundaries $\partial E_{i,j}$ and $\partial S_{i,j}\setminus \{(i,j),(i+1,j),(i,j+1),(i+1,j+1)\}$ is called a critical point. A point $(i,j)\in \mathbb{N}\times \mathbb{N}$ is a corner point. We say the line $\pi [i]\times [1,n]$ is the free-space diagram boundary defined by ${\pi }_i$ (and analogous for ${\sigma }_i$). We say the strip $[i,i+1]\times [1,n]$ is the $i$th column, and the strip $[1,n]\times [i,i+1]$ is the $i$th row. We say a critical point $p$ is a row (resp. column) critical point if $p$ lies on a vertical (resp. horizontal) boundary.

In this and the next section, we describe our ideas using an intuitive class of transformations: translation in ${ℝ}^2$. Specifically, we determine whether there exists a translation vector $t=\lambda \overrightarrow{v}$ such that $d_{ℱ}(\pi ,\sigma +t)\le \delta$, where $\lambda \in {ℝ}_{\ge 0}$ and $\overrightarrow{v}$ is a unit vector. For this, we first describe how to transform the free-space reachability problem into a graph reachability problem.

Using the free-space diagram $𝒟={𝒟}_{\delta }(\pi ,\sigma )$, we construct a refined free-space diagram (see Figure 1, left). Let $l({\pi }_i)$ (resp. $l({\sigma }_j)$) be the vertical (resp. horizontal) boundary of $𝒟$ defined by ${\pi }_i$ (resp. ${\sigma }_j$). For every critical point $p$ on the boundaries, we draw a perpendicular grid line $l(p)$ through $p$. Note that by definition, a critical point does not coincide with a corner point of $𝒟$. If $p$ lies on the horizontal boundary, $l(p)$ is a vertical line; otherwise, $l(p)$ is a horizontal line. The refined free-space diagram includes all grid lines, the free-space diagram boundaries, and their intersections. For simplicity, we redefine ${𝒟}_{\delta }(\pi ,\sigma )$ to denote the refined free-space diagram. Let the intersection between a grid line and a free-space boundary be a propagated critical point.

Using the refined free-space diagram ${𝒟}_{\delta }(\pi ,\sigma )$, we construct a refined free-space graph (refined FSG or FSG for short) ${𝒢}^f={𝒢}_{\delta }^f(\pi ,\sigma )$ as follows (see Figure 1, right). For every intersection between a grid line and a free-space boundary, add a boundary vertex. For every intersection between two grid lines, add an interior vertex. For every intersection between two free-space boundaries, add a corner vertex. Note that each vertex in ${𝒢}^f$ is uniquely defined by an ordered pair $(p,q)$, where $l(p)$ is vertical and $l(q)$ is horizontal; $p$ (resp. $q$) is either a vertex of $\pi$ (resp. $\sigma$) or a critical point in $𝒟$ – let $\text{v}(\mathrm{p},\mathrm{q})$ denote such vertex in ${𝒢}^f$. Each vertex is assigned a weight that is either 1 or 0. For every vertex $u=\text{v}(\mathrm{p},\mathrm{q})$, if $a=l(p)\cap l(q)$ lies on a boundary of the free-space diagram, we set $\text{w}(\mathrm{u})=1$ if $a$ lies in the free-space or $\text{w}(\mathrm{u})=0$ otherwise. We set the weights of the rest of the vertices, the interior vertices, to $1$. We say a vertex $u$ is activated if $\text{w}(\mathrm{u})=1$ or deactivated if $\text{w}(\mathrm{u})=0$. We say a vertex $\text{v}({\pi }_{\mathrm{i}},\cdot )$ (resp. $\text{v}(\cdot ,{\sigma }_{\mathrm{j}})$) lies on the free-space graph boundary defined by ${\pi }_i$ (resp. ${\sigma }_j$).

To construct edges, we use the geometric positions of the grid lines and the FSG boundaries. For vertices in ${𝒢}^f$ defined by every grid line or FSG boundary $l(p)$, add a directed edge $(\text{v}(\mathrm{p},\mathrm{q}),\text{v}(\mathrm{p},{\mathrm{q}}^{\prime }))$ to ${𝒢}^f$ if $l(q)$ is immediately below $l(q^{\prime })$. If $l(q)$ and $l(q^{\prime })$ overlap, break ties arbitrarily. Analogously, add a directed edge $(\text{v}(\mathrm{p},\mathrm{q}),\text{v}({\mathrm{p}}^{\prime },\mathrm{q}))$ if $l(p)$ is immediately to the left of $l(p^{\prime })$. A path $P\subseteq {𝒢}^f$ is an ordered subset $\{(a_1,b_1),\mathrm{\dots },(a_m,b_m)\}$ of edges where $b_i=a_{i+1}$, . We say $P$ is a feasible path if $a_1=\text{v}({\pi }_1,{\sigma }_1)$, $b_m=\text{v}({\pi }_{\mathrm{n}},{\sigma }_{\mathrm{n}})$, and $\text{w}({\mathrm{a}}_{\mathrm{i}})=\text{w}({\mathrm{b}}_{\mathrm{i}})=1$ for all values of $i$. When $a_1$ and $b_m$ are specified, $P$ is a feasible path if $P$ uses exclusively activated vertices. We say a FSG ${𝒢}^f$ is $st$-reachable if there exists a feasible path in ${𝒢}^f$ from $\text{v}({\pi }_1,{\sigma }_1)$ to $\text{v}({\sigma }_{\mathrm{n}},{\pi }_{\mathrm{n}})$. The following lemma naturally is derived from the properties of the free-space diagram (see the full version for the proof).

Now consider translating $\sigma$ along $\overrightarrow{v}$. As $\sigma$ translates continuously, the FSG also changes, and we would like to know how these changes affect the $st$-reachability of ${𝒢}^f$. To do this, we track the following free-space events. See Figure 2 for visualizations of these row free-space events.

For now, we assume that we are given an ordered set $T=\{t_1,t_2,\mathrm{\dots },t_m\}$ of translations, where $t_i={\lambda }_i\overrightarrow{v}$, ${\lambda }_i\in {ℝ}_{\ge 0}$, and ${\lambda }_i\le {\lambda }_{i+1}$. We further assume that $T$ is complete, which is defined as follows.

Here, $\sigma +t$ denotes the curve obtained by adding the translation vector $t$ to $\sigma$. To update the free-space graph to reflect the state of the free-space diagram, we define the following free-space graph operations. Let $R(p)$ be the set of vertices defined by $l(p)$, and let $R(p)[i]$ denote the $i$th vertex, where $i\ge 1$.

We show that we can update the FSG ${𝒢}_{\delta }^f(\pi ,\sigma +t_{i-1})$ to ${𝒢}_{\delta }^f(\pi ,\sigma +t_i)$ using a constant number of free-space graph operations, plus processing time. For these updates, we will distinguish between a corner vertex operation and a boundary vertex operation. We use corner vertex operations to handle VE event updates, and boundary vertex operations to handle VVE event updates.

In this section, using the refined FSG ${𝒢}^f={𝒢}_{\delta }^f(\pi ,\sigma )$, we define a grid graph ${𝒢}^g={𝒢}_{\delta }^g(\pi ,\sigma )$. We then show that ${𝒢}^f$ is $st$-reachable if and only if ${𝒢}^g$ is $st$-reachable. An advantage of the newly defined grid graph is that its number of vertices does not change under updates. We show that the structural changes implied by the FSG operations can be simulated by simply modifying the weights in the grid graph, without needing to add or remove vertices. These features of the grid graph allow us to use the offline dynamic grid reachability result in [14] to obtain a faster update and query time.

The grid graph ${𝒢}^g$ contains all vertices of the free-space graph ${𝒢}^f$. In addition to the free-space graph ${𝒢}^f$, we add a set of placeholder vertices to the grid graph ${𝒢}^g$ so as to maintain the same number of vertices in the grid graph ${𝒢}^g$ under updates. Refer to Figure 3 for an illustration. We define the placeholder vertices. Let $m_i^r$ (resp. $m_i^c)$ be the number of row critical points in the $i$th row (resp. column) of $𝒟={𝒟}_{\delta }(\pi ,\sigma )$. We define a family of ordered sets $\{H_1^r,\mathrm{\dots },H_{n-1}^r\}$ of row placeholder points. Each set $H_i^r$ contains exactly $2n-m_i^r+2$ points, and let $H_i^r[j]$ denote the $j$th point for $1\le j\le 2n-m_i^r+2$. The family of ordered sets of column placeholder points $\{H_1^c,\mathrm{\dots },H_{n-1}^c\}$ are analogously defined. For a row (resp. column) placeholder point $h$, the placeholder line $l(h)$ is horizontal (resp. vertical). Note that the placeholder points and lines are abstractly defined as they do not exist in $𝒟$.

Finally, define $\text{v}(\mathrm{p},\mathrm{q})$ to be a placeholder vertex if $p$ is either a vertex of $\pi$, a critical point, or a placeholder point, and $q$ is also either a vertex of $\sigma$, a critical point, or a placeholder point. Add the placeholder vertex $\text{v}(\mathrm{p},\mathrm{q})$ to ${𝒢}^g$. The weight of a placeholder vertex on a boundary matches the weight of the adjacent corner vertex either directly above or to its right. Specifically, for every $h$ in every $H_i^r$ and every point $p$ in the union of the vertices of $\pi$ and row critical points, we set $\text{w}(\text{v}(\mathrm{p},\mathrm{h}))=\text{w}(\text{v}({\pi }_{\mathrm{i}},{\sigma }_{\mathrm{j}+1}))$ if $p={\pi }_i$, otherwise we set $\text{w}(\text{v}(\mathrm{p},\mathrm{h}))=1$. Analogously, for every $h\in H_i^c$, we set $\text{w}(\text{v}(\mathrm{h},\mathrm{q}))=\text{w}(\text{v}({\pi }_{\mathrm{i}+1},{\sigma }_{\mathrm{j}}))$ if $q={\sigma }_j$. Otherwise, we set $\text{w}(\text{v}(\mathrm{h},\mathrm{q}))=1$. This completes the definition of placeholder vertices.

To define the edges in ${𝒢}^g$, we define the ordering of the placeholder lines among the grid lines and the free-space boundaries. The lowest placeholder line $l(H_i^r[1])$ lies above all grid lines $l(p)$, where $p$ is a row critical point on the $i$th row. The placeholder line $l(H_i^r[j+1])$ is above $l(H_i^r[j])$. The free-space boundary $l({\sigma }_{i+1})$ is above the highest placeholder line $l(H_i^r[2n-m_i^r+2])$. The ordering involving vertical placeholder lines is analogously defined. The set of placeholder lines defined by $H_i^c$ are between $l({\pi }_{i+1})$ and the rightmost grid line in the $i$th column.

For vertices in ${𝒢}^g$ defined by $l(p)$, add a directed edge $(\text{v}(\mathrm{p},\mathrm{q}),\text{v}(\mathrm{p},{\mathrm{q}}^{\prime }))$ to ${𝒢}^g$ if $l(q)$ is immediately below $l(q^{\prime })$ and add a directed edge $(\text{v}(\mathrm{q},\mathrm{p}),\text{v}({\mathrm{q}}^{\prime },\mathrm{p}))$ to ${𝒢}^g$ if $l(q)$ is immediately to the left of $l(q^{\prime })$. If $l(q)$ and $l(q^{\prime })$ overlap, then break ties using the same ordering as in ${𝒢}^f$. Add additional diagonal directed edge $(\text{v}(\mathrm{p},\mathrm{q}),\text{v}({\mathrm{p}}^{\prime },{\mathrm{q}}^{\prime }))$ if $p$ is immediately to the left of $p^{\prime }$ and $q$ is immediately below $q^{\prime }$. Note that a vertex defined by two placeholder points is simultaneously a placeholder vertex as well as an interior vertex.

Next, we check that our construction fits the grid graph definition of [14]. An $N\times N$ grid graph consists of vertices numbered from $(1,1)$ to $(N,N)$ and edges from vertex $(i,j)$ to each of vertices $(i+1,j)$, $(i,j+1)$, and $(i+1,j+1)$, where the weight of a vertex is either $1$ or $0$. By construction, every of $n-1$ rows in ${𝒟}_{\delta }(\pi ,\sigma )$ contains exactly $2n$ critical points and placeholder points combined. Together with $n$ horizontal boundaries, there are $N=2n\cdot (n-1)+n=2n^2-n$ horizontal lines. For the same reasons, there are $N$ vertical lines. Clearly, ${𝒢}_{\delta }^g(\pi ,\sigma )$ is an $N\times N$ grid graph.

Before proving that ${𝒢}_{\delta }^f(\pi ,\sigma )$ and ${𝒢}_{\delta }^g(\pi ,\sigma )$ are equivalent in terms of $st$-reachability, we first show that a feasible path $P\subseteq {𝒢}^g$ has several desired properties. Recall from Section 3 that a feasible path is bi-monotone and only passes through activated vertices. By the monotonicity of a feasible path and the convexity of the free-space in a cell, we observe the following (see the full version for the proof).

Due to the properties of ${𝒢}^g$, a diagonal edge in a path $P$ can be replaced by using the rectilinear edges in the same “cube”. Furthermore, if the final vertex $b$ of a subpath $P_j\subseteq P$ is a placeholder vertex, we can transform $P_j$ such that it ends at a non-placeholder vertex. We have the following lemma.

In this section, we consider a class $𝒯$ of transformations that is rationally parameterized or rationally represented with $k$ degrees of freedom as defined by Wenk [56]. The set of rationally parameterized transformations is a subset of affine transformations, and an affine transformation is composed of a linear transformation and a translation. In the definition below, the pair $(A,t)$ represents the affine transformation obtained by composing a linear transformation $A$, given as a $d\times d$ matrix, and a translation $t$, given as a $d$-dimensional vector.

Let ${ℝ}^k$ be the parameter space of $𝒯$. For $x\in {ℝ}^k$, let ${\tau }_x$ denote the transformation defined by the $k$-tuple $x$ of parameters. Let $\pi$ and $\sigma$ be two $d$-dimensional polygonal curves. Let ${\tau }_x(\sigma )$ be the resulting curve by applying the transformation ${\tau }_x$ to $\sigma$.

In ${ℝ}^k$, a vertex-vertex-edge (VVE) critical transformation ${𝒯}_{\delta }^{vve}({\pi }_i,{\pi }_j,\overline{{\sigma }_w})$ is the union of every point $x\in {ℝ}^k$ such that the segment ${\tau }_x(\overline{{\sigma }_w})$ lies on the intersection of the boundary of the $d$-spheres centered at ${\pi }_i$ and ${\pi }_j$, respectively, and it is formally defined as follows.