# Faster Fréchet Distance Under Transformations

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, Sampson Wong

To cite this version:

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, Sampson Wong. Faster Fréchet Distance Under Transformations. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), Jul 2025, Aarhus, Denmark. 10.4230/LIPIcs.ICALP.2025.36 . hal-05317485

HAL Id: hal-05317485

https://hal.science/hal-05317485v1

Submitted on 16 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Faster Fréchet Distance Under Transformations

Kevin Buchin

<figure><img src="image_2.png" /></figure>

Technical University of Dortmund, Germany

Maike Buchin

<figure><img src="image_3.png" /></figure>

Ruhr University Bochum, Germany

Zijin Huang

<figure><img src="image_4.png" /></figure>

University of Sydney, Australia

André Nusser

<figure><img src="image_5.png" /></figure>

Université Côte d'Azur, CNRS, Inria, Sophia Antipolis, France

Sampson Wong

<figure><img src="image_6.png" /></figure>

BARC, University of Copenhagen, Denmark

## Abstract

We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves $\pi$ and $\sigma$ of total complexity $n$ and a threshold $\delta \ge 0$, we present an $\tilde{O}(n^{7+\frac{1}{3}})$ time algorithm to determine whether there exists a translation $t \in \mathbb{R}^2$ such that the Fréchet distance between $\pi$ and $\sigma + t$ is at most $\delta$. This improves on the previous best result, which is an $O(n^8)$ time algorithm.

We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class $\mathcal{T}$ of rationally parametrized transformations with $k$ degrees of freedom, we show that one can determine whether there is a transformation $\tau \in \mathcal{T}$ such that the Fréchet distance between $\pi$ and $\tau(\sigma)$ is at most $\delta$ in $\tilde{O}(n^{3k+\frac{4}{3}})$ time.

**2012 ACM Subject Classification** Theory of computation $\rightarrow$ Computational geometry

**Keywords and phrases** Fréchet distance, curve similarity, shape matching

**Digital Object Identifier** 10.4230/LIPIcs.ICALP.2025.36

**Category** Track A: Algorithms, Complexity and Games

**Related Version** Full Version: https://arxiv.org/abs/2501.12814

**Funding** André Nusser: This work was supported by the French government through the France 2030 investment plan managed by the National Research Agency (ANR), as part of the Initiative of Excellence of Université Côte d'Azur under reference number ANR-15-IDEX-01.

**Sampson Wong:** This work was supported by the European Union under a Marie Skłodowska-Curie Actions (MSCA) Postdoctoral Fellowship Grant number 101146276.

## 1 Introduction

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,

<figure><img src="image_7.png" /></figure>

© Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong; licensed under Creative Commons License CC-BY 4.0

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025).

Editors: Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Article No. 36; pp. 36:1–36:20

<figure><img src="image_8.png" /></figure>

Leibniz International Proceedings in Informatics
LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<figure><img src="image_9.png" /></figure>
36:2 Faster Fréchet Distance Under Transformations

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 $\mathbb{R}^2$, an $\tilde{O}(n^{10})$ time algorithm<fnref n="1" /> for the Fréchet
distance under translation was presented in [35], and an $\tilde{O}(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 $\tilde{O}(n^5)$ time, or for affine
transformations in $d$ dimensions in $\tilde{O}(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 $\tilde{O}(n^6)$-time algorithm [45] was developed, then an $\tilde{O}(n^5)$-time
algorithm [7], and more recently, an $\tilde{O}(n^{4+\frac{2}{3}})$-time algorithm [14].

Our Contribution

In this paper, we present the first progress on the Fréchet distance under transformations
since its introduction [4, 35, 47, 56]. Similar to the algorithm in [4, 56], our algorithm can
be used for a wide range of classes of transformations. Specifically, given two curves $\pi$
and $\sigma$ of total complexity $n$ and a threshold $\delta \ge 0$, we want to determine whether there is
a transformation $\tau$ from a given class of transformations, such that the Fréchet distance
between $\pi$ and $\tau(\sigma)$ is at most $\delta$. Our algorithm improves the running time for translations
in two dimensions from $O(n^8)$ to $\tilde{O}(n^{7+\frac{1}{3}})$.

► **Theorem 1.** *The Fréchet distance under translation in $\mathbb{R}^2$ can be decided in $O(n^{7+\frac{1}{3}} \log^2 n)$ time.*

More generally, we improve the running time for the various classes of transformations
(and dimensions) given by Wenk [56] by roughly a factor of $n^{2/3}$. For example, for rotations
or scalings in $\mathbb{R}^2$, our algorithm runs in $\tilde{O}(n^{4+\frac{1}{3}})$ time and for affine transformations in $d$
dimensions in $\tilde{O}(n^{3(d^2+d)+\frac{4}{3}})$ time.

► **Theorem 2.** *The Fréchet distance under transformations rationally represented with $k$ degrees of freedom can be decided in $O(n^{3k+4/3} \log^2 n)$ time.*

We first present our approach for the special case of translations in two dimensions. Then
we generalize our approach to other transformations and higher dimensions. Similarly to
the approach in [4], we compute an arrangement in the space of transformations, which in
the case of 2D translations has complexity $O(n^6)$. In [4], the Fréchet distance is computed
for each face of this arrangement in $O(n^2)$ time per face by using the *free-space diagram*,
which results in an overall running time of $O(n^8)$. In our approach, we instead traverse the
arrangement, making use of the fact that the free-space diagram for adjacent faces in the
arrangement is similar. The challenge with using this approach is that it requires a dynamic
data structure for maintaining reachability in the free-space diagram. However, already on
directed graphs this is a difficult problem that to the best of our knowledge mostly saw

<footnote n="1">¹ By $\tilde{O}(\cdot)$ we hide (poly-)logarithmic factors in $n$.</footnote>
progress on planar graphs [32, 46, 50] or more specifically grid graphs [7, 14]. In [14], a data structure with efficient updates and queries for reachability in a dynamic directed grid graph is presented, which is used to give a faster algorithm for the discrete Fréchet distance under translation. However, while the discrete Fréchet distance naturally reduces to a reachability problem on such a grid, this is not the case for the (continuous) Fréchet distance.

To that end, we present a detailed analysis of the changes in the free-space diagram when traversing the arrangement in the space of translations, which we call *events* (see Section 3). We then show how to construct a (directed) *free space graph* from the free-space diagram, and analyze how the free-space graph changes for the various types of events. Then, we show how each of these events can be modeled as changes in a suitable grid graph, which allows us to utilize the data structure in [14] to maintain reachability in this graph (see Section 4). The main challenge here is that an event may cause rows or columns in the free-space graph to swap, appear or disappear, which are not operations that can be handled by the previous data structure of [14]. Using our approach, we show how to handle these row or column events using a linear number of updates to the grid graph per event. Finally, we use an amortized analysis to show that each event only requires a constant number of updates to the grid graph per event, since expensive events do not happen too often.

We note that in an independent work, progress was made on the one-dimensional Fréchet distance under translation or scaling [9]. In that work, the authors present an $\tilde{O}(n^{8/3})$ algorithm for both problems, making use of the offline dynamic data structure of [14].

## 2 Preliminaries

A $d$-dimensional polygonal curve $\pi$ is a piecewise linear curve represented as a continuous mapping from $[1, n]$ to $\mathbb{R}^d$. For integer $i$, $\pi_i = \pi[i]$ is a vertex, and $\bar{\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 **width**$f,g(\pi, \sigma)$ between two curves $\pi$ and $\sigma$ with respect to the reparameterizations $f$ and $g$, is defined as follows.

$$ width_{f,g}(\pi, \sigma) = \max_{t \in [0,1]} \|\pi(f(t)) - \sigma(g(t))\| $$

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_F(\pi, \sigma)$ is the minimum leash length required over all possible walks (defined by reparameterizations $f$ and $g$).

$$ d_F(\pi, \sigma) = \inf_{f,g \in [0,1] \to [0,1]} width_{f,g}(\pi, \sigma) $$

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 $\mathcal{F}_\delta(\pi, \sigma)$ is a collection of points in $\mathbb{R}^2$ in the range $[1, n] \times [1, n]$. A point $(x, y)$ is in the free-space if the Euclidean norm (distance) $\|\pi(x) - \sigma(y)\|$ 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 \mathcal{F}_\delta(\pi, \sigma)$ the *forbidden space*.

$$ \mathcal{F}_\delta(\pi, \sigma) = \{(x, y) \in [1, n] \times [1, n] \mid \|\pi(x) - \sigma(y)\| \le \delta\} $$
36:4 Faster Fréchet Distance Under Transformations

The free-space diagram $\mathcal{D} = \mathcal{D}_{\delta}(\pi, \sigma)$ is the partition of the free-space into $n \times n$ cells. A cell $C_{i,j}$ in $\mathcal{D}$ 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_{\mathcal{F}}(\pi, \sigma) \le \delta$ if and only if there is a bi-monotone path in $\mathcal{D}_{\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 ith column, and the strip $[1, n] \times [i, i+1]$ is the ith row. We say a critical point *p* is a row (resp. column) critical point if *p* lies on a vertical (resp. horizontal) boundary.

3 From free-space reachability to graph reachability

In this and the next section, we describe our ideas using an intuitive class of transformations: translation in $\mathbb{R}^2$. Specifically, we determine whether there exists a translation vector $t = \lambda \vec{v}$ such that $d_{\mathcal{F}}(\pi, \sigma + t) \le \delta$, where $\lambda \in \mathbb{R}_{\ge 0}$ and $\vec{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 $\mathcal{D} = \mathcal{D}_{\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 $\mathcal{D}$ 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 $\mathcal{D}$. 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 $\mathcal{D}_{\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*.

<figure><img src="image_10.png" /><figcaption>■ **Figure 1** From the refined free-space diagram to the refined free-space graph. On the left free-space diagram (FSD), the corner points, critical points, and propagated critical points are marked by squares, blue circles, and red circles, respectively. On the right free-space diagram graph (FSG), the corner, boundary, and interior vertices are marked by squares, circles, and crosses, respectively.</figcaption></figure>

Using the refined free-space diagram $\mathcal{D}_{\delta}(\pi, \sigma)$, we construct a *refined free-space graph* (refined FSG or FSG for short) $\mathcal{G}^f = \mathcal{G}_{\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 $G^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 $\mathcal{D}$ – let $\mathbf{v}(p, q)$ denote such vertex in $G^f$. Each vertex is assigned a weight that is either 1 or 0. For every vertex $u = \mathbf{v}(p, q)$, if $a = l(p) \cap l(q)$ lies on a boundary of the free-space diagram, we set $\mathbf{w}(u) = 1$ if $a$ lies in the free-space or $\mathbf{w}(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 $\mathbf{w}(u) = 1$ or deactivated if $\mathbf{w}(u) = 0$. We say a vertex $\mathbf{v}(\pi_i, \cdot)$ (resp. $\mathbf{v}(\cdot, \sigma_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 $G^f$ defined by every grid line or FSG boundary $l(p)$, add a directed edge $(\mathbf{v}(p, q), \mathbf{v}(p, q'))$ to $G^f$ if $l(q)$ is immediately below $l(q')$. If $l(q)$ and $l(q')$ overlap, break ties arbitrarily. Analogously, add a directed edge $(\mathbf{v}(p, q), \mathbf{v}(p', q))$ if $l(p)$ is immediately to the left of $l(p')$. A path $P \subseteq G^f$ is an ordered subset $\{(a_1, b_1), \dots, (a_m, b_m)\}$ of edges where $b_i = a_{i+1}, \forall 1 \le i < m$. We say $P$ is a feasible path if $a_1 = \mathbf{v}(\pi_1, \sigma_1), b_m = \mathbf{v}(\pi_n, \sigma_n)$, and $\mathbf{w}(a_i) = \mathbf{w}(b_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 $G^f$ is st-reachable if there exists a feasible path in $G^f$ from $\mathbf{v}(\pi_1, \sigma_1)$ to $\mathbf{v}(\sigma_n, \pi_n)$. The following lemma naturally is derived from the properties of the free-space diagram (see the full version for the proof).

**Lemma 3.** The FSG $G^f = \mathcal{G}_{\delta}^f(\pi, \sigma)$ is st-reachable if and only if $d_{\mathcal{F}}(\pi, \sigma) \le \delta$.

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

**Definition 4.** We define the following row free-space events. Column free-space events are defined analogously.

1. A Vertex-edge (VE) event is defined by a pair $(p, \overline{\sigma_w})$, where $p$ is either a vertex of $\pi$ or $p$ is a row critical point in row $w$.

a. Entering/leaving event: the corner point $p$ enters or leaves the free-space.

b. Appearing/disappearing event: the grid line $l(p)$ appears or disappears as the critical point $p$ appears or disappears.

2. A Vertex-vertex-edge (VVE) event is defined by a triplet $(p, q, \overline{\sigma_w})$, where $p$ and $q$ are row critical points in row $w$.

a. Overlapping event: two grid lines $l(p)$ and $l(q)$ overlap.

b. Separating event: two overlapping grid lines $l(p)$ and $l(q)$ no longer overlap.

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

**Definition 5.** We say the ordered set $T = \{t_1, \dots, t_m\}$ of translations is complete if $\mathcal{G}_{\delta}^f(\pi, \sigma + t_i)$ and $\mathcal{G}_{\delta}^f(\pi, \sigma + t_{i+1})$ differ by exactly one free-space event, for all $1 \le i < m$.

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$.
36:6 Faster Fréchet Distance Under Transformations

<figure><img src="image_11.png" /><figcaption>Figure 2 In the top row of figures, as the segment $σ_1σ_2$ translates, the critical points $p$ and $q$ moves down and up, respectively. As $l(p)$ and $l(q)$ (colored in blue) move, they overlap and then separate. In the bottom row, as $σ_1σ_2$ translates, a new critical point $p'$ appears, and then a new critical point $p''$ appears.</figcaption></figure>

**Definition 6.** We define the following free-space graph operations.

- Vertex operation: either activate or deactivate a vertex of $G^f$.

- Row operation: either insert or delete a row of $G^f$. Column operations are defined analogously.

- To insert a row $R(p)$ of vertices between adjacent rows $R(p_a)$ and $R(p_b)$, add a vertex $v(q,p)$ for every $q$, where $q$ is either a critical point on a horizontal FSG boundary or a vertex of $\pi$. For every $1 \le i < |R(p_a)|$,

1. remove the edge $(R(p_b)[i], R(p_a)[i])$,

2. add horizontal edge $(R(p)[i], R(p)[i+1])$, and

3. add vertical edges $(R(p_b)[i], R(p)[i])$ and $(R(p)[i], R(p_a)[i])$.

- To remove the row $R(p)$ of vertices, remove $R(p)$ and their adjacent edges. For every $1 \le i \le |R(p_a)|$, add edges $(R(p_b)[i], R(p_a)[i])$.

We show that we can update the FSG $G^f_\delta(\pi, \sigma + t_{i-1})$ to $G^f_\delta(\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.

**Lemma 7.** Let $G^f_i = G^f_\delta(\pi, \sigma + t_i)$. Given $G^f_{i-1}$, to compute $G^f_i$, it takes

- $O(1)$ time and $O(1)$ corner vertex operations if $t_i$ is an entering/leaving event,

- $O(1)$ time and $O(1)$ boundary vertex operations if $t_i$ is an overlapping or separating event,

- $O(n)$ time plus $O(1)$ row operations if $t_i$ is an appearing/disappearing event.

**Proof.** If $t_i$ is an entering/leaving event, we simply set the weight of the respective corner vertex to either 1 or 0. If $t_i$ is a VVE event defined by $(p, q, \bar{\sigma}_w)$, let $p$ and $q$ lie on the $i$th and $j$th free-space boundary, respectively. Observe that when a VVE event occurs, among all vertices partly defined by $p$ or $q$, only the weights of vertices $v(\pi_i, p)$, $v(\pi_j, p)$, $v(\pi_i, q)$, and $v(\pi_j, q)$ change. It is sufficient to spend $O(1)$ time to determine and update their weights, by computing cells $C_{i,w}$ and $C_{j,w}$ from scratch.
If $t_i$ is an appearing/disappearing event in the $j$th row, it takes linear time to recompute the row critical points in this row. Then, it takes linear time to compute the grid lines $l(p_a)$ and $l(p_b)$ that $l(p)$ lie between by recomputing the cells in the $j$th row. Once $l(p_a)$ and $l(p_b)$ is identified, it takes exactly one row insertions or deletions to update $G_{i-1}^f$ to $G_i^f$. Therefore, it takes $O(n)$ time plus a constant number of row operations. ◀

Using a naive implementation, in the worst case, a row operation can take $\Omega(n^2)$ time since there are $\Omega(n^2)$ vertical grid lines. Determining st-reachability takes $\Omega(n^4)$ time, since there are $\Omega(n^4)$ vertices in the FSG. Hence, using the FSG directly would not result in a faster algorithm. In the next section, we fix these issues by defining an “equivalent” grid graph in which updates and queries can be done more efficiently than the naive implementation.

## 4 From free-space graph reachability to grid graph reachability

In this section, using the refined FSG $G^f = G_\delta^f(\pi, \sigma)$, we define a grid graph $G^g = G_\delta^g(\pi, \sigma)$. We then show that $G^f$ is st-reachable if and only if $G^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^g$ contains all vertices of the free-space graph $G^f$. In addition to the free-space graph $G^f$, we add a set of placeholder vertices to the grid graph $G^g$ so as to maintain the same number of vertices in the grid graph $G^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 $\mathcal{D} = \mathcal{D}_\delta(\pi, \sigma)$. We define a family of ordered sets $\{H_1^r, ..., 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, ..., 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 $\mathcal{D}$.

Finally, define $\mathbf{v}(p, 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 $\mathbf{v}(p, q)$ to $G^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 $\mathbf{w}(\mathbf{v}(p, h)) = \mathbf{w}(\mathbf{v}(\pi_i, \sigma_{j+1}))$ if $p = \pi_i$, otherwise we set $\mathbf{w}(\mathbf{v}(p, h)) = 1$. Analogously, for every $h \in H_i^c$, we set $\mathbf{w}(\mathbf{v}(h, q)) = \mathbf{w}(\mathbf{v}(\pi_{i+1}, \sigma_j))$ if $q = \sigma_j$. Otherwise, we set $\mathbf{w}(\mathbf{v}(h, q)) = 1$. This completes the definition of placeholder vertices.

To define the edges in $G^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^g$ defined by $l(p)$, add a directed edge $(\mathbf{v}(p, q), \mathbf{v}(p, q'))$ to $G^g$ if $l(q)$ is immediately below $l(q')$ and add a directed edge $(\mathbf{v}(q, p), \mathbf{v}(q', p))$ to $G^g$ if $l(q)$ is immediately to the left of $l(q')$. If $l(q)$ and $l(q')$ overlap, then break ties using the same ordering as in
36:8 Faster Fréchet Distance Under Transformations

<figure><img src="image_12.png" /><figcaption>■ **Figure 3** A visual illustration of the placeholder lines and their relative positions among the grid lines and the free-space diagram boundaries. The row (resp. column) placeholder points and lines are colored in red (resp. green). The grid lines are colored in blue.</figcaption></figure>

$G^f$. Add additional diagonal directed edge $(v(p, q), v(p', q'))$ if $p$ is immediately to the left of $p'$ and $q$ is immediately below $q'$. 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 $\mathcal{D}_\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, $G_\delta^g(\pi, \sigma)$ is an $N \times N$ grid graph.

Before proving that $G_\delta^f(\pi, \sigma)$ and $G_\delta^g(\pi, \sigma)$ are equivalent in terms of st-reachability, we first show that a feasible path $P \subseteq G^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).

► **Observation 8.** Let $P$ be a feasible path in $G^g$. If $P$ contains a corner vertex $v(\pi_i, \sigma_j)$, then let $l(p_l)$ and $l(p_r)$ be the first grid lines that are not placeholder lines to the left and right of $l(\pi_i)$, respectively. Similarly, let $l(p_a)$ and $l(p_b)$ be the first grid line above and below $l(\sigma_j)$ respectively. Then, we have either $w(v(p_l, \sigma_j)) = 1$ or $w(v(\pi_i, p_b)) = 1$. Analogously, we have either $w(v(\pi_i, p_a)) = 1$ or $w(v(p_r, \sigma_j)) = 1$.

Due to the properties of $G^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.

► **Lemma 9.** If there is a feasible path $P$ in a grid graph $G^g$, there is a feasible path $P'$ in $G^g$ with the following properties.

1. $P'$ does not contain diagonal edges.

2. For every $1 \le j \le n$, the first vertex of $P'$ partly defined by $\sigma_j$ is not a placeholder vertex.
**Proof.** We first replace the diagonal edges in $P$. Consider a diagonal edge $(a, b) \in P$ in the “cube”, where $(a, c_t)$ and $(c_b, b)$ are the vertical edges, and $(a, c_b)$ and $(c_t, b)$ are horizontal edges. Observe that by construction, either both $a$ and $b$ lie on the boundaries, or at least one of them is an interior vertex. If both $a$ and $b$ lie on the boundaries, either $c_b$ or $c_t$ must be activated, since the opposite would contradict either Observation 8 or the convexity of the free-space in a cell.

If $a$ is an interior vertex, we consider the following cases. If $b$ is also an interior vertex, then so are $c_t$ and $c_b$ with weight 1, and we replace $(a, b)$ with $(a, c_t)$ and $(c_t, b)$. If $b$ is a boundary vertex, then either $c_b$ or $c_t$ is an interior vertex, and we replace $(a, b)$ with either $(a, c_b)$ and $(c_b, b)$ or $(a, c_t)$ and $(c_t, b)$. The more interesting case is when $b = v(\pi_{i+1}, \sigma_{j+1})$ is a corner vertex. In this case, $c_b = v(\pi_{i+1}, h \in H_i^c)$, and by construction, $w(c_b) = w(b) = 1$. We replace $(a, b)$ with $(a, c_b)$ and $(c_b, b)$.

If $b$ is an interior vertex, we use similar case distinctions. If $a$ is an interior vertex, $c_b$ must also be an interior vertex. If $a$ is a boundary vertex lying on the left (resp. bottom) boundary, then $c_b$ (resp. $c_t$) is an interior vertex. The more interesting case is where $a = v(\pi_i, \sigma_j)$ is a corner vertex. In this case, both $c_b$ and $c_t$ are boundary vertices. By Observation 8, at least one of them (say $c_b$) has weight 1, and we replace $(a, b)$ with $(a, c_b)$ and $(c_b, b)$.

<figure><img src="image_13.png" /><figcaption>■ **Figure 4** A path $P_{j-1}$ ending at a placeholder vertex $b$ can be transformed to end at a non- placeholder vertex $c$.</figcaption></figure>

With $P$ containing exclusively rectilinear edges, we partition $P$ into subpaths lying on different rows (see Figure 4). Specifically, let $P_j \subseteq P$ be the subpath containing the first vertex $a$ defined by $\sigma_j$ and the first vertex $b$ defined by $\sigma_{j+1}$. We first transform $P_j$ to guarantee that $b$ is not defined by a placeholder point. Let $b = v(h \in H_i^c, \sigma_{j+1})$, and note that $w(b) = w(\pi_{i+1}, \sigma_{j+1}) = 1$. Let $l(p')$ be immediately to the left of $l(H_i^c[1])$. By Observation 8, $w(c = v(p', \sigma_{j+1})) = 1$. Combining this argument with the fact that all interior vertices have weight 1 and the rectilinearity of $P$, we can transform $P_j$ to end at $c$, and $P_{j+1}$ to start at $c$. Since the first vertex $v(\pi_1, \sigma_1)$ and the final vertex $v(\pi_n, \sigma_n)$ of $P$ are not defined by a placeholder vertex, once we apply the transformation above, the first vertex of every subpath $P_j$ is not defined by a placeholder vertex. The proof is complete. ◀

We next observe that if there is a path in $G^g$ that does not use a placeholder vertex, the path also exists in $G^f$. Indeed, excluding the placeholder lines, $G^g$ and $G^f$ use the same set of grid lines and FSG boundaries, and the same ordering.

► **Observation 10.** If there is a path $P$ in $G^g = G_\delta^g(\pi, \sigma)$ such that $P$ does not use any placeholder vertices or diagonal edges, then $P$ also exists in $G^f = G_\delta^f(\pi, \sigma)$.

To demonstrate that $G^f$ and $G^g$ are equivalent with respect to st-reachability, we first note that any feasible path in $G^g$ corresponds to a feasible path in $G^f$. Specifically, given a subpath $P \subseteq G^g$ that traverses the “strip” defined by a single set of placeholder points, we can always construct a corresponding subpath $Q \subseteq G^f$ such that $Q$ starts and ends at the same vertices as $P$. We have Lemma 11 and 12.
36:10 Faster Fréchet Distance Under Transformations

**Lemma 11.** Let $P$ be a path in $\mathcal{G}^g = \mathcal{G}_\delta^g(\pi, \sigma)$. Let $P$ start at a non-placeholder vertex $\mathbf{v}(p, \sigma_j)$. Let $(\mathbf{v}(p', q'), \mathbf{v}(p', H_j^r[1]))$ be the last edge of $P$, where $q' \neq H_j^r[1]$. There exists a path $Q$ from $\mathbf{v}(p, \sigma_j)$ to $\mathbf{v}(p', q')$ in $\mathcal{G}^f = \mathcal{G}_\delta^f(\pi, \sigma)$.

<figure><img src="image_14.png" /><figcaption>■ **Figure 5** A path $Q_i$ in $\mathcal{G}^f$ can be constructed by connecting the vertex $b_i$ where $P_i$ ends and the vertex $a_{i+1}$ where $P_{i+1}$ starts.</figcaption></figure>

**Proof.** Let $\{P_1, \dots, P_u\}$ be the subpaths of $P$ generated by removing all placeholder vertices from $P$ (see Figure 5). For $1 \le i \le u$, let $P_i$ be a path starting from $a_i$ and ending at $b_i$. By Observation 10, the path $P_i$ also exists in $\mathcal{G}^f$. Since the placeholder vertices are removed, every $a_i$ or $b_i$ is either a boundary vertex or an interior vertex. Since the interior vertices have weight 1, a path $Q_i$ from $b_i$ to $a_{i+1}$ exists in $\mathcal{G}^f$. We set $Q = (\cup_{1 \le i \le u-1} P_i \cup Q_i) \cup P_u$ to complete the proof. ◀

**Lemma 12.** Let $P$ be a path in $\mathcal{G}^g = \mathcal{G}_\delta^g(\pi, \sigma)$. Let $(\mathbf{v}(p, q), \mathbf{v}(p, H_j^r[1]))$ be the first edge of $P$, and let $P$ ends at a non-placeholder vertex $\mathbf{v}(p', \sigma_{j+1})$. There exists a path $Q$ from $\mathbf{v}(p, q)$ to $\mathbf{v}(p', \sigma_{j+1})$ in $\mathcal{G}^f = \mathcal{G}_\delta^f(\pi, \sigma)$.

**Proof.** If $P$ does not contain a vertex defined by any vertical boundary, then the lemma trivially holds as the interior vertices have weight 1. Otherwise, $P$ contains a set of vertices defined by $\{\pi_u, \dots, \pi_w\}$ in increasing order of indices. By Observation 8 and convexity of the free-space in a cell, there is a path $P_1$ in $\mathcal{G}^f$ from $\mathbf{v}(p, q)$ to $\mathbf{v}(\pi_u, \sigma_{j+1})$, and a path $P_2$ from $\mathbf{v}(\pi_w, \sigma_{j+1})$ to $\mathbf{v}(p', \sigma_{j+1})$.

Since $P$ uses only activated vertices, for every $u \le i \le w$, $\mathbf{w}(\mathbf{v}(\pi_i, h)) = 1$ for some $h \in H_j^r$. By construction of $\mathcal{G}^g$, $\mathbf{v}(\pi_i, h)$ is activated if and only if $\mathbf{v}(\pi_i, \sigma_{j+1})$ is activated, whose weight must also be 1. By the convexity of the free-space within a cell, since $\mathbf{v}(\pi_i, \sigma_{j+1})$ and $\mathbf{v}(\pi_{i+1}, \sigma_{j+1})$ are activated, for every $l(p)$ lying between $l(\pi_i)$ and $l(\pi_{i+1})$, the vertex $\mathbf{v}(p, \sigma_{j+1})$ is activated. Therefore, $\forall u \le i \le w$, there is a path $P_i \subset \mathcal{G}^f$ from $\mathbf{v}(\pi_i, \sigma_{j+1})$ to $\mathbf{v}(\pi_{i+1}, \sigma_{j+1})$ using activated vertices. We set $Q = P_1 \cup (\cup_{u \le i \le w} P_i) \cup P_2$ to complete the proof. ◀

We are finally ready to show that $\mathcal{G}^f$ and $\mathcal{G}^g$ are equivalent in terms of st-reachability.

**Lemma 13.** There exists a feasible path $P^f$ in the free-space graph $\mathcal{G}_\delta^f(\pi, \sigma)$ if and only if there exists a feasible path $P^g$ in the grid graph $\mathcal{G}_\delta^g(\pi, \sigma)$.

**Proof.** First, we observe that if there is a feasible path $P^f \subseteq \mathcal{G}^f$, then there is a feasible path $P^g \subseteq \mathcal{G}^g$. Consider a partition of $P^f$ into subpaths lying in different cells of the free-space diagram. Let the subpath $P_{i,j}^f \subseteq P$ start from the vertex $a$ to the vertex $b$, where $a$ lies on the bottom or left boundary of $C_{i,j}$, and $b$ lies on the top or right boundary of $C_{i,j}$. Since the interior vertices have weight 1, and a diagonal edge can be used if $b$ is a corner vertex, there is a path $P_{i,j}^g \subseteq \mathcal{G}^g$ from $a$ to $b$ using activated vertices.
Second, we show that if there is a feasible path $P^g \subseteq \mathcal{G}^g$, then there is a feasible path $P^f \subseteq \mathcal{G}^f$. We use an analogous argument where we construct a feasible path $P^f$ using subpaths in $P^g$. By Lemma 9, we know that $P^g$ uses exclusively rectilinear edges. Furthermore, by the same Lemma 9, $P^g$ can be partitioned into subpaths $\{P_1^g, \dots, P_{n-1}^g\}$ such that $\forall 1 \le j \le n-1$, $P_j^g$ starts at a non-placeholder vertex $a = \mathbf{v}(p, \sigma_j)$, and ends at another non-placeholder vertex $b = \mathbf{v}(p', \sigma_{j+1})$. We partition $P_j^g$ using its first edge $(a', b')$, where vertex $a'$ is partly defined by a placeholder point $H_j^r[1]$. By Lemma 11, there is a path $P_j^{fa}$ in $\mathcal{G}^f$ from $a$ to $a'$. By Lemma 12, there is a path $P_j^{fb}$ in $\mathcal{G}^f$ from $a'$ to $b$. We set $P_j^f = P_j^{fa} \cup P_j^{fb}$ and $P^f = \cup_j P_j^f$ to complete the proof. ◀

Now, we show that free-space graph operations can be implemented in the grid graph efficiently. Recall from Lemmas 6 and 7 that corner vertex operations activate or deactivate a vertex of $\mathcal{G}^f$ given an entering or leaving event, boundary vertex operations activate or deactivate a vertex of $\mathcal{G}^f$ given an overlapping or separating event, and row operations insert or delete a row of $\mathcal{G}^f$ given an appearing or disappearing event.

**Lemma 14.** Let $\mathcal{G}_i^g$ be the associated grid graph of the free-space graph $\mathcal{G}_i^f$. Let $u$ be a free-space graph operation that updates $\mathcal{G}_1^f$ to $\mathcal{G}_2^f$. To update $\mathcal{G}_1^g$ to $\mathcal{G}_2^g$, it is sufficient to update the weights of at most:

- $O(n)$ vertices if $u$ is a corner vertex operation,

- $O(1)$ vertices if $u$ is a boundary vertex operation, or

- $O(n)$ vertices if $u$ is a row operation.

**Proof.** If $u$ is a corner vertex operation activating a corner vertex $\mathbf{v}(\pi_i, \sigma_j)$, we activate $\mathbf{v}(\pi_i, \sigma_j)$ in $\mathcal{G}^g$. Then, we activate $\mathbf{v}(\pi_i, h_1)$ for every $h_1 \in H_{j-1}^r$, and activate $\mathbf{v}(h_2, \sigma_j)$ for every $h_2 \in H_{i-1}^c$. Since there are at most a linear number of placeholder points defined per row and column, this operation requires us to change the weights of $O(n)$ vertices in $\mathcal{G}^g$. If $u$ activates a boundary vertex $a$, we simply activate $a$ in $\mathcal{G}^g$. If $u$ deactivates a vertex, we use analogous procedure.

If $u$ is a boundary vertex operation, to insert a row of vertices while maintain the properties of the grid graph, we take advantage of the fact that the intersection between the free-space and a cell boundary is a single interval. Specifically, to insert $R(p)$ of vertices below $R(p_a)$ and above $R(p_b)$ in row $j$, let the critical point $p$ lie on the $i'$th vertical boundary. For $1 \le i \le n$, if $i = i'$, then set $\mathbf{w}(\mathbf{v}(\pi_{i'}, H_j^r[1])) = 1$. For every other value of $i$, set $\mathbf{w}(\mathbf{v}(\pi_i), H_j^r[1]) = 1$, if the weights of both $\mathbf{v}(\pi_i, p_a)$ and $\mathbf{v}(\pi_i, p_b)$ are 1. Otherwise, set $\mathbf{w}(\mathbf{v}(\pi_i), H_i^r[1]) = 0$. Reduce the size of $H_j^r$ by one by removing $H_j^r[1]$.

We prove the correctness of the boundary vertex operation by showing that this insertion process maintains the properties of the grid graph. First, the total number of row critical points plus the placeholder points stays the same. Second, it is sufficient to determine the weight of $\mathbf{v}(\pi_i, p)$ by checking the weights of $\mathbf{v}(\pi_i, p_a)$ and $\mathbf{v}(\pi_i, p_a)$. Both intersections $l(\pi_i) \cap l(p_a)$ and $l(\pi_i) \cap l(p_b)$ need to lie in the free-space for $l(\pi_i) \cap l(p)$ to lie in the free-space, since the opposite suggests that there is a grid line between $l(p_a)$ and $l(p_b)$, contradicting the assumption that $l(p_a)$ and $l(p_b)$ are adjacent.

If $u$ is a row operation, to delete $R(p)$ lying in the $j$th row, let $l(q)$ be the first grid line below $l(H_j^r[1])$. For all $1 \le i \le n$, set $\mathbf{w}(\mathbf{v}(\pi_i, q)) = \mathbf{w}(\mathbf{v}(\pi_i, \sigma_j))$. Insert a new placeholder point at the beginning of $H_j^r$ by setting $H_j^r[1] = q$. This process also maintains the properties of the grid graph. Column operations uses analogous arguments. ◀
36:12 Faster Fréchet Distance Under Transformations

Given $G_{i-1}^g = G_\delta^g(\pi, \sigma + t_{i-1})$ and event $t_i$, we can now transform $G_{i-1}^g$ to $G_i^g$. Specifically, in Lemma 7, we have shown that if $t_i$ is a VE event, it takes $O(n)$ time plus $O(1)$ corner vertex operations or row operations. If $t_i$ is a VVE event, it takes $O(1)$ time plus $O(1)$ boundary vertex operations. By combining Lemma 7 and Lemma 14, we can bound the number of vertex weight changes for each free-space event type.

**Lemma 15.** Given $G_\delta^g(\pi, \sigma + t_{i-1})$ and the next event $t_i$, to compute $G_\delta^g(\pi, \sigma + t_i)$, it takes $O(n)$ vertex weight changes if $t_i$ is a VE event, or $O(1)$ vertex weight changes if $t_i$ is a VVE event.

We can now summarize Sections 3 and 4 and state the main lemma of this section. In Lemma 3, we have shown that the Fréchet distance $d_\mathcal{F}(\pi, \sigma)$ is at most $\delta$ if and only if the refined free-space graph $G^f = G_\delta^f(\pi, \sigma)$ is st-reachable. In Section 4, for each $G^f$, we have defined an associate grid graph $G^g = G_\delta^g(\pi, \sigma)$. In Lemma 13, we have shown that $G^g$ is st-reachable if and only if $G^f$ is st-reachable. Combining the above with Lemma 15, we have the following.

**Lemma 16.** Let $T = \{t_1, ..., t_m\}$ be a complete set of free-space events containing exclusively $m_{vve}$ VVE events and $m_{ve}$ VE events. Let $N = 2n^2 - n$, and let $T_u(N)$ (resp. $T_q(N)$) be the time complexity to update (resp. query st-reachability) in an $N \times N$ grid graph. It takes

$$O(N^2 + (m_{ve} \cdot n + m_{vve}) \cdot T_u(N) + m \cdot T_q(N))$$

time to determine if there exists $t_i \in T$ such that $d_\mathcal{F}(\pi, \sigma + t_i) \le \delta$.

Using the results by Alt, Knauer and Wenk [4], we can build an arrangement in the translation space. Using this arrangement, we can compute a set of complete events (translations) $T$ containing exclusively $O(n^6)$ VVE events and $O(n^5)$ VE events. They have shown that it is sufficient to consider only translations in $T$ to determine if there is a translation $t$ such that $d_\mathcal{F}(\pi, \sigma + t) \le \delta$.

To obtain fast updates and queries in the grid graph, we use the offline dynamic grid reachability result of Bringmann, Künnemann and Nusser [14]. The problem is defined as follows. We start from a directed $N \times N$-grid graph, and we are given a set $\{u_1, ..., u_U\}$ of updates such that each update $u_i$ is to either activate or deactivate a vertex. For $1 \le i \le U$, the goal is to compute after each update $u_i$ whether there is a feasible path from vertex $v(1, 1)$ to $v(N, N)$. Their result is as follows.

**Fact 17 ([14, Theorem 3.4]).** Offline dynamic grid reachability can be solved in time $O(N^2 + UN^{2/3} \log^2 N)$.

We analyze the running time. In total, we require $O(n^6)$ vertex updates for $G^g$, and we can update a vertex and perform st-reachability queries in amortized $O(N^{2/3} \cdot \log^2 N) = O(n^{4/3} \cdot \log^2 n)$ time. Plugging these running times into Lemma 16 we obtain the following theorem.

**Theorem 1.** The Fréchet distance under translation in $\mathbb{R}^2$ can be decided in $O(n^{7+1/3} \log^2 n)$ time.

5 Fréchet distance under transformation

In this section, we consider a class $\mathcal{T}$ 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.

**► Definition 18** ([56, Definition 25]). Let $1 \le k \le d^2+d$, and let $p_1, \dots, p_{d^2+d}, q_1, \dots, q_{d^2+d} \in \mathbb{R}[X_1, \dots, X_k]$ be $2(d^2+d)$ polynomials of constant degree in $k$ variables, such that $q_i(x) \ne 0$ for all $1 \le i \le d^2+d$ and for all $x \in \mathbb{R}^k$. Let $r_i := p_i/q_i$ for all $1 \le i \le d^2+d$, such that $r_i(x) := p_i(x)/q_i(x)$ for all $x \in \mathbb{R}^k$. If

$$ \mathcal{T} = \left\{ \begin{pmatrix} r_1(x) & \dots & r_d(x) \\ r_{d+1}(x) & \dots & r_{2d}(x) \\ \vdots & \ddots & \vdots \\ r_{d^2-d+1}(x) & \dots & r_{d^2}(x) \end{pmatrix}, \begin{pmatrix} r_{d^2+1}(x) \\ r_{d^2+2}(x) \\ \vdots \\ r_{d^2+d}(x) \end{pmatrix} \middle| x \in \mathbb{R}^k \right\} $$

then we call $\mathcal{T}$ rationally parameterized or rationally represented with $k$ degrees of freedom (dof). $\mathbb{R}^k$ is called the parameter space of $\mathcal{T}$.

Let $\mathbb{R}^k$ be the parameter space of $\mathcal{T}$. For $x \in \mathbb{R}^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 $\mathbb{R}^k$, a vertex-vertex-edge (VVE) critical transformation $\mathcal{T}_{\delta}^{vve}(\pi_i, \pi_j, \overline{\sigma_w})$ is the union of every point $x \in \mathbb{R}^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.

$$ \mathcal{T}_{\delta}^{vve}(\pi_i, \pi_j, \overline{\sigma_w}) = \{x \in \mathbb{R}^k \mid \exists z \in \overline{\sigma_w}, \|\tau_x(z) - \pi_i\| = \|\tau_x(z) - \pi_j\| = \delta\} $$

Analogously, a vertex-edge (VE) critical transformation $\mathcal{T}_{\delta}^{ve}(\pi_i, \overline{\sigma_w})$ is the union of every point $x \in \mathbb{R}^k$ such that the segment $\tau_x(\overline{\sigma_w})$ lies on the boundary of the $d$-ball centered at $\pi_i$, and it is formally defined as follows.

$$ \mathcal{T}_{\delta}^{ve}(\pi_i, \overline{\sigma_w}) = \{x \in \mathbb{R}^k \mid \exists z \in \overline{\sigma_w}, \|\tau_x(z) - \pi_i\| = \delta\} $$

Every critical transformation is a semi-algebraic set in $\mathbb{R}^k$. Using $\mathcal{O}(n^3)$ VVE critical transformations and $\mathcal{O}(n^2)$ VE critical transformations, Wenk [56, Proof of Theorem 8] showed that they can build an arrangement $\mathcal{A}_\delta$ in $\mathbb{R}^k$, in time $\mathcal{O}(n^{3k})$ and using $\mathcal{O}(n^{3k})$ space. Furthermore, $\mathcal{A}_\delta$ contains at most $\mathcal{O}(n^{3k})$ $k'$-dimensional faces for $0 \le k' \le k-1$. Let $\tau_F = \tau_x$ be the transformation that is represented by an arbitrary parameter $x \in F$. In [56, Lemma 24], Wenk showed that if there exists some transformation $\tau$ such that $d_F(\pi, \tau(\sigma)) < \delta$, then there exists some $k'$-dimensional face $F \in \mathcal{A}_\delta$ such that for any $\tau_F$, $d_F(\pi, \tau_F(\sigma)) \le \delta$. Their results are summarized as follows.

**► Fact 19.** Given a pair of polygonal curves $\pi$ and $\sigma$, a real number $\delta \ge 0$, and a class $\mathcal{T}$ of transformations that is rationally represented with $k$ degrees of freedom, one can build an arrangement $\mathcal{A}_\delta = \mathcal{A}_\delta(\pi, \sigma, \mathcal{T})$ using at most $\mathcal{O}(n^3)$ VVE critical transformations and $\mathcal{O}(n^2)$ VE critical transformations. The arrangement $\mathcal{A}_\delta$ has in total $\mathcal{O}(n^{3k})$ complexity, and it can be constructed in $\mathcal{O}(n^{3k})$ time using $\mathcal{O}(n^{3k})$ space. To determine if there exists a transformation $\tau \in \mathcal{T}$ such that $d_F(\pi, \tau(\sigma)) \le \delta$, it is sufficient to check exactly one transformation $\tau_F$ for every $k'$-dimensional face $F \in \mathcal{A}_\delta$, where $0 \le k' \le k-1$.

Once the arrangement $\mathcal{A}_\delta$ is constructed, the remainder of the previous algorithm in Wenk [56] is straightforward. For every face $F \in \mathcal{A}_\delta$, sample a point $x \in F$, and determine if $d_F(\pi, \tau_x(\sigma)) \le \delta$ using classic algorithms (Alt and Godau [2] for example). In total, this takes $\mathcal{O}(n^{3k} \cdot n^2)$ time.
To obtain a running time improvement, we use a similar approach to previous sections. We generate a complete set of events as follows. Initialize an empty graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$. For every face $F \in \mathcal{A}_\delta$, add a vertex $v_F$ to $\mathcal{V}$. For every two adjacent faces $F$ and $F'$, add an edge $(v_F, v_{F'})$ to $\mathcal{E}$. For each vertex $v_F$, record a transformation $\tau_F$. Next, we compute a complete set of events using $\mathcal{G}$. Initialize an empty set of events $T$. Then, use a DFS to compute a spanning tree of $\mathcal{G}$, and perform a Euler tour over the spanning tree starting from an arbitrary vertex. For each directed edge $e = (v_{F'}, v_F)$ in the tour, we add an event only if we enter or leave a critical transformation. More specifically, let $B(F)$ be the set of critical transformations adjacent to face $F$. If $B(F) \setminus B(F') = \{\mathcal{T}_c\}$, we say *e traverses into* the critical transformation $\mathcal{T}_c$ via $F$. If $B(F') \setminus B(F) = \{\mathcal{T}_c\}$, we say *e traverses out of* the critical transformation $\mathcal{T}_c$ via $F$.

Let $D(p)$ be the $d$-sphere of radius $\delta$ centered at $p$. Depending on the cases where $e$ traverse into or out of a VVE or VE critical transformation, we add the respective free-space events defined in Definition 4.

1. If $\mathcal{T}_c$ is a VVE critical transformation $\mathcal{T}_\delta^{vve} = \mathcal{T}_\delta^{vve}(\pi_i, \pi_j, \bar{\sigma}_w)$, we compute $p = D(\pi_i) \cap \tau_F(\bar{\sigma}_w)$ and $q = D(\pi_j) \cap \tau_F(\bar{\sigma}_w)$, and append an event $t$ defined by $(p, q, \bar{\sigma}_w)$ to $T$. If $e$ traverses into $\mathcal{T}_c$, $t$ is an overlapping event. If $e$ traverses out of $\mathcal{T}_\delta^{vve}$, $t$ is a separating event.

2. If $\mathcal{T}_c$ is a VE critical transformation $\mathcal{T}_\delta^{ve} = \mathcal{T}_\delta^{ve}(\pi_i, \bar{\sigma}_w)$, we compute $p = D(\pi_i) \cap \bar{\sigma}_w$, and we append an event $t$ represented by $(p, \bar{\sigma}_w)$ to $T$. If $e$ traverses into $\mathcal{T}_c$, $t$ is an entering event if $p = \pi_i$, or an appearing event if $p \neq \pi_i$. Analogously, if $e$ traverses out of $\mathcal{T}_c$, $t_e$ is a leaving event if $p = \pi_i$, or a disappearing event if $p \neq \pi_i$.

We say an event $t$ is associated with the critical transformation $\mathcal{T}_c$ and the edge $e$, if $t$ is computed from an edge $e$ traversing into or out of $\mathcal{T}_c$. We show that $T$ has two desired properties.

**Lemma 20.** Given the arrangement $\mathcal{A}_\delta = \mathcal{A}_\delta(\pi, \sigma, T)$, one can compute a complete set $T = \{t_1, \dots, t_{O(n^{3k})}\}$ of free-space events in $O(n^{3k})$ time with the following properties.

1. Every face in $\mathcal{A}_\delta$ is associated with at least one event in $T$.

2. For each event $t_i$ associated with edge $(v_F, v_{F'}) \in \mathcal{E}$, $\mathcal{G}_\delta^f(\pi, \tau_F(\sigma))$ and $\mathcal{G}_\delta^f(\pi, \tau_{F'}(\sigma))$ differ by exactly one free-space event.

**Proof.** Note that $\mathcal{G}$ is connected and contains a vertex $v_F$ for every face $F \in \mathcal{A}_\delta$. The Euler tour that we constructed over $\mathcal{G}$ visits every vertex of $\mathcal{G}$, and hence every face of $\mathcal{A}_\delta$, at least once. Moreover, note that a pair of adjacent faces in $\mathcal{A}_\delta$ is separated by exactly one critical arrangement, which we recall is a semi-algebraic set in $\mathbb{R}^k$. Therefore, any edge $(v_F, v_{F'})$ in the Euler tour traverses exactly one critical transformation, that is, the transformation associated with the critical arrangement separating the adjacent faces $F$ and $F'$.

We next argue that the free-space graph does not change unless a free-space event occurs. It is clear that unless an appearing or disappearing event occurs, neither the vertices nor the edges in a free-space graph $\mathcal{G}^f$ change. What remains is to argue that the vertex weights do not change unless an event occurs. More specifically, unless a free-space event occurs, no intersection $a = l(p) \cap l(q)$ enter or leave the free-space.

For the sake of contradiction, say that $a$ either enters or leaves the free-space and a free-space event does not occur. Clearly, $v(p, q)$ cannot be a corner vertex, as the weight change is explicitly captured by the entering/leaving event. $v(p, q)$ cannot be an interior vertex, as every interior vertex has weight 1 regardless.
Therefore, $\mathbf{v}(p, q)$ is a boundary vertex and $a$ is a critical point. Without loss of generality, let $p$ be a vertex of $\pi$. If $a$ enters the free-space, $a$ must coincide with a critical point $b = l(p') \cap l(q)$, so grid lines $l(p)$ and $l(p')$ overlap. If $a$ leaves the free-space, $a$ must first coincide with (again say) $b$, so the grid lines $l(p)$ and $l(p')$ separate. In both cases, either an overlapping event occurs or a separating event occurs, contradicting the assumption.

Let $p$ (resp. $q$) be a critical point on the $i$th (resp. $j$th) free-space boundary. We next argue that no free-space event occurs unless we traverse into or out of a critical transformation. This is true by the definition. An entering/appearing (resp. leaving/disappearing) event defined by $(p, \bar{\pi}_w)$ occurs only when the associated edge $(v_F, v_{F'})$ traverses into (resp. out of) the critical transformation $\mathcal{T}_{\delta}^{ve}(\pi_i, \bar{\sigma}_w)$. An overlapping (resp. separating) event defined by $(p, q, \bar{\sigma}_w)$ occurs only when $(v_F, v_{F'})$ traverses into (resp. out of) the critical transformation $\mathcal{T}_{\delta}^{vve}(\pi_i, \pi_j, \bar{\sigma}_w)$.

Observe that exactly one free-space event occurs every time we traverse into or out of a critical transformation, which is captured by the Euler tour. Therefore, every face is associated with at least one event in $T$, and for every edge $(v_F, v_{F'})$ associated with an event $t \in T$, $G^f(\pi, \tau_F(\sigma))$ and $G^f(\pi, \tau_{F'}(\sigma))$ differ by exactly one event. ◀

We also observe that fewer faces are adjacent to VE critical transformations than to VVE critical transformations (see the full version for the proof).

**Observation 21.** In the arrangement $\mathcal{A}_{\delta} = \mathcal{A}_{\delta}(\pi, \sigma, \mathcal{T})$, there are at most $O(n^{3k})$ faces adjacent to VVE critical transformations, and $O(n^{3k-1})$ faces adjacent to VE critical transformations.

We are now ready to put the pieces together to obtain a faster algorithm for computing the Fréchet distance under rationally parameterized transformations. Given a real number $\delta \ge 0$, a class $\mathcal{T}$ of transformations rationally represented with $k$ degrees of freedom, and a pair of polygonal curves $\pi$ and $\sigma$, each with $n$ vertices, it was shown in Wenk [56] that it is sufficient to construct an arrangement $\mathcal{A}_{\delta}$ in the parameter space $\mathbb{R}^k$ and sample a transformation from each face. In Lemma 20, we showed that we can traverse this arrangement and generate a complete set of $O(n^{3k})$ free-space events in $O(n^{3k})$ time. Our results in Section 3 and 4 for handling free-space events under translations also extend to handling free-space events under rationally parameterized transformations, and therefore we can plug in the number of updates to Lemma 16. Our algorithm takes $O(n^4 + n^{3k} \cdot (T_u(n^2) + T_q(n^2)))$ time, where $T_u(n^2)$ is the time complexity to update a vertex and $T_q(n^2)$ is the time complexity to query st-reachability in an $O(n^2) \times O(n^2)$-grid graph. For a fast query time $T_q(n^2)$, we again use the result of Bringmann, Künnemann and Nusser [14], which we restate for convenience.

**Fact 22** ([14, Theorem 3.4], restate of Fact 17). Offline dynamic grid reachability can be solved in time $O(N^2 + UN^{2/3} \log^2 N)$.

By Fact 22, $T_u(n^2) + T_q(n^2)$ takes amortized $O(n^{4/3} \log^2 n)$ time. For classes of rationally parameterized transformations with at least one degree of freedom, we state our final result.

**Theorem 2.** *The Fréchet distance under transformations rationally represented with $k$ degrees of freedom can be decided in $O(n^{3k+4/3} \log^2 n)$ time.*

# 6 Conclusion

Our algorithm provides the first progress in over 20 years for computing the (continuous) Fréchet distance under transformations. The running time comes from traversing an arrangement in the space of transformations, performing an update to a dynamic grid graph data structure in each step.
36:16 Faster Fréchet Distance Under Transformations

We conclude with open questions. Can the update time be reduced? Improving the
update time for the data structure of [14] would directly improve our running time. But
it may also be possible to tailor the data structure for our setting. For instance, we could
prune the lower levels of the data structure, since reachability in the inside of free space cells
does not carry any information.

Can we prove a non-trivial conditional lower bound for computing the Fréchet distance under translations? The complexity of the arrangement, Ω(n^6), would seem like a natural lower bound. However, even transferring the n^{4-o(1)} conditional lower bound for the discrete Fréchet distance under translation [14] to the (continuous) Fréchet distance seems difficult, since the lower bound construction crucially relies on the fact that the discrete Fréchet traversal can only stay on the vertices and not on the edges.

References

1 Helmut Alt. The computational geometry of comparing shapes. In Susanne Albers, Helmut Alt, and Stefan Näher, editors, *Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday*, volume 5760 of *Lecture Notes in Computer Science*, pages 235–248. Springer, 2009. doi:10.1007/978-3-642-03456-5_16.

2 Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. *International Journal of Computational Geometry & Applications*, 05:75–91, 1995. doi:10.1142/S0218195995000064.

3 Helmut Alt and Leonidas J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, *Handbook of Computational Geometry*, chapter 3, pages 121–153. North Holland / Elsevier, 2000. doi:10.1016/B978-044482537-7/50004-8.

4 Helmut Alt, Christian Knauer, and Carola Wenk. Matching polygonal curves with respect to the Fréchet distance. In *Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS)*, pages 63–74. Springer, 2001. doi:10.1007/3-540-44693-1_6.

5 Helmut Alt, Ludmila Scharf, and Sven Scholz. Probabilistic matching and resemblance evaluation of shapes in trademark images. In *Proc. 6th ACM International Conference on Image and Video Retrieval (CIVR)*, pages 533–540. ACM, 2007. doi:10.1145/1282280.1282357.

6 Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. Discrete Fréchet distance oracles. In *Proc. 40th International Symposium on Computational Geometry (SoCG)*, volume 293 of *LIPICS*, pages 10:1–10:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.10.

7 Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. A faster algorithm for the discrete Fréchet distance under translation. *CoRR*, abs/1501.03724, 2015. arXiv:1501.03724.

8 Julian Baldus and Karl Bringmann. A fast implementation of near neighbors queries for Fréchet distance (GIS Cup). In *Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems*, SIGSPATIAL’17, pages 99:1–99:4, New York, NY, USA, 2017. ACM. doi:10.1145/3139958.3140062.

9 Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, and Marena Richter. Transforming dogs on the line: On the Fréchet distance under translation or scaling in 1D. In *Proceedings of the 41st International Symposium on Computational Geometry (SoCG)*, 2025. arXiv:2501.12821. doi:10.48550/arXiv.2501.12821.

10 Lotte Blank and Anne Driemel. A faster algorithm for the Fréchet distance in 1d for the imbalanced case. In *Proc. 32nd Annual European Symposium on Algorithms (ESA)*, volume 308 of *LIPICS*, pages 28:1–28:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ESA.2024.28.

11 Karl Bringmann and Bhaskar Ray Chaudhury. Polyline simplification has cubic complexity. *J. Comput. Geom.*, 11(2):94–130, 2020. doi:10.20382/JOCG.V11I2A5.
12 Karl Bringmann, Anne Driemel, André Nusser, and Ioannis Psarros. Tight bounds for approximate near neighbor searching for time series under the Fréchet distance. In *Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 517–550. SIAM, 2022. doi: 10.1137/1.9781611977073.25.

13 Karl Bringmann, Marvin Künnemann, and André Nusser. When lipschitz walks your dog: Algorithm engineering of the discrete fréchet distance under translation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, *28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference)*, volume 173 of LIPIcs, pages 25:1–25:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ESA.2020.25.

14 Karl Bringmann, Marvin Künnemann, and André Nusser. Discrete Fréchet distance under translation: Conditional hardness and an improved algorithm. *ACM Trans. Algorithms*, 17(3):25:1–25:42, 2021. doi:10.1145/3460656.

15 Karl Bringmann, Marvin Künnemann, and André Nusser. Walking the dog fast in practice: Algorithm engineering of the fréchet distance. *J. Comput. Geom.*, 12(1):70–108, 2021. doi: 10.20382/JOCG.V12I1A4.

16 Frederik Brüning, Jacobus Conradi, and Anne Driemel. Faster approximate covering of subcurves under the Fréchet distance. In *Proc. 30th Annual European Symposium on Algorithms (ESA)*, volume 244 of LIPIcs, pages 28:1–28:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ESA.2022.28.

17 Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo. Detecting commuting patterns by clustering subtrajectories. *International Journal of Computational Geometry & Applications*, 21(03):253–282, June 2011. doi:10.1142/S0218195911003652.

18 Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong. Map-matching queries under Fréchet distance on low-density spanners. In *Proc. 40th International Symposium on Computational Geometry (SoCG)*, volume 293 of LIPIcs, pages 27:1–27:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.27.

19 Kevin Buchin, Yago Diez, Tom van Diggelen, and Wouter Meulemans. Efficient trajectory queries under the Fréchet distance (GIS Cup). In *Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems*, SIGSPATIAL’17, pages 101:1–101:4, New York, NY, USA, 2017. ACM. doi:10.1145/3139958.3140064.

20 Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, and Martijn Struijs. Approximating $(k, \ell)$-center clustering for curves. In *Proc. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 2922–2938. SIAM, 2019. doi:10.1137/1.9781611975482.181.

21 Kevin Buchin, Anne Driemel, Natasja van de L’Isle, and André Nusser. klcluster: Center-based clustering of trajectories. In Farnoush Banaei Kashani, Goce Trajcevski, Ralf Hartmut Güting, Lars Kulik, and Shawn D. Newsam, editors, *Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2019, Chicago, IL, USA, November 5-8, 2019*, pages 496–499. ACM, 2019. doi:10.1145/3347146.3359111.

22 Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, and Marcel Roeloffzen. Fréchet distance for uncertain curves. *ACM Trans. Algorithms*, 19(3):29:1–29:47, 2023. doi:10.1145/3597640.

23 Kevin Buchin, Brittany Terese Fasy, Erfan Hosseini Sereshgi, and Carola Wenk. On length-sensitive Fréchet similarity. In *Proc. 18th International Symposium on Algorithms and Data Structures (WADS)*, volume 14079 of Lecture Notes in Computer Science, pages 208–231. Springer, 2023. doi:10.1007/978-3-031-38906-1_15.

24 Kevin Buchin, Maarten Löffler, Tim Ophelders, Aleksandr Popov, Jérôme Urhausen, and Kevin Verbeek. Computing the Fréchet distance between uncertain curves in one dimension. *Comput. Geom.*, 109:101923, 2023. doi:10.1016/J.COMGEO.2022.101923.
36:18 Faster Fréchet Distance Under Transformations

25 Kevin Buchin, Tim Ophelders, and Bettina Speckmann. SETH says: Weak Fréchet distance is faster, but only if it is continuous and in one dimension. In Proc. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2887–2901. SIAM, 2019. doi:10.1137/1.9781611975482.179.

26 Maike Buchin, Anne Driemel, and Dennis Rohde. Approximating (k, l)-median clustering for polygonal curves. ACM Trans. Algorithms, 19(1):4:1–4:32, 2023. doi:10.1145/3559764.

27 Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals. Efficient Fréchet distance queries for segments. In Proc. 30th Annual European Symposium on Algorithms (ESA), volume 244 of LIPIcs, pages 29:1–29:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ESA.2022.29.

28 Siu-Wing Cheng and Haoqiang Huang. Curve simplification and clustering under Fréchet distance. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1414–1432. SIAM, 2023. doi:10.1137/1.9781611977554.CH51.

29 Siu-Wing Cheng and Haoqiang Huang. Fréchet distance in subquadratic time. CoRR, abs/2407.05231, 2024. To appear at SODA 2025. doi:10.48550/arXiv.2407.05231.

30 Siu-Wing Cheng and Haoqiang Huang. Solving Fréchet distance problems by algebraic geometric methods. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4502–4513. SIAM, 2024. doi:10.1137/1.9781611977912.158.

31 Connor Colombe and Kyle Fox. Approximating the (continuous) Fréchet distance. In Proc. 37th International Symposium on Computational Geometry (SoCG), volume 189 of LIPIcs, pages 26:1–26:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.SOCG.2021.26.

32 Krzysztof Diks and Piotr Sankowski. Dynamic plane transitive closure. In Lars Arge, Michael Hoffmann, and Emo Welzl, editors, Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, volume 4698 of Lecture Notes in Computer Science, pages 594–604. Springer, 2007. doi:10.1007/978-3-540-75520-3_53.

33 Anne Driemel, Ivor van der Hoog, and Eva Rotenberg. On the discrete Fréchet distance in a graph. In Proc. 38th International Symposium on Computational Geometry, (SoCG), volume 224 of LIPIcs, pages 36:1–36:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.SOCG.2022.36.

34 Fabian Dütsch and Jan Vahrenhold. A filter-and-refinement-algorithm for range queries based on the Fréchet distance (GIS Cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL’17, pages 100:1–100:4, New York, NY, USA, 2017. ACM. doi:10.1145/3139958.3140063.

35 Alon Efrat, Piotr Indyk, and Suresh Venkatasubramanian. Pattern matching for sets of segments. Algorithmica, 40(3):147–160, 2004. doi:10.1007/S00453-004-1089-Y.

36 Chenglin Fan and Benjamin Raichel. Computing the Fréchet gap distance. Discrete & Computational Geometry, 65(4):1244–1274, June 2021. doi:10.1007/s00454-020-00224-w.

37 Arnold Filtser and Omrit Filtser. Static and streaming data structures for Fréchet distance queries. ACM Trans. Algorithms, 19(4):39:1–39:36, 2023. doi:10.1145/3610227.

38 Arnold Filtser, Omrit Filtser, and Matthew J. Katz. Approximate nearest neighbor for curves: Simple, efficient, and deterministic. Algorithmica, 85(5):1490–1519, 2023. doi:10.1007/S00453-022-01080-1.

39 Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk. On flipping the Fréchet distance. In Proc. 14th Innovations in Theoretical Computer Science Conference (ITCS), volume 251 of LIPIcs, pages 51:1–51:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ITCS.2023.51.

40 Emily Fox, Amir Nayyeri, Jonathan James Perry, and Benjamin Raichel. Fréchet edit distance. In Proc. 40th International Symposium on Computational Geometry (SoCG), volume 293 of LIPIcs, pages 58:1–58:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.58.
41 Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Computing a Subtrajectory Cluster from c-Packed Trajectories. In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:15, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ISAAC.2023.34.

42 Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong. Map matching queries on realistic input graphs under the Fréchet distance. In Proc. 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1464–1492. SIAM, 2023. doi:10.1137/1.9781611977554.CH53.

43 Joachim Gudmundsson, André van Renssen, Zeinab Saeidi, and Sampson Wong. Translation invariant Fréchet distance queries. Algorithmica, 83(11):3514–3533, 2021. doi:10.1007/S00453-021-00865-0.

44 Joachim Gudmundsson and Sampson Wong. Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 173–189. SIAM, 2022. doi:10.1137/1.9781611977073.9.

45 Minghui Jiang, Ying Xu, and Binhai Zhu. Protein structure-structure alignment with discrete Fréchet distance. In Proc. 5th Asia-Pacific Bioinformatics Conference (APBC), volume 5 of Advances in Bioinformatics and Computational Biology, pages 131–141. Imperial College Press, 2007. URL: http://www.comp.nus.edu.sg/%7Ewongls/psZ/apbc2007/apbc162a.pdf.

46 Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 95:1–95:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPICS.ICALP.2024.95.

47 Christian Knauer. Algorithms for Comparing Geometric Patterns. PhD thesis, Free University Berlin, 2002. doi:10.17169/refubium-16312.

48 Abhinandan Nath and Erin Taylor. k-median clustering under discrete Fréchet and hausdorff distances. In Proc. 36th International Symposium on Computational Geometry (SoCG), volume 164 of LIPIcs, pages 58:1–58:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.SOCG.2020.58.

49 E. Sriraghavendra, K. Karthik, and Chiranjib Bhattacharyya. Fréchet distance based approach for searching online handwritten documents. In Proc. 9th International Conference on Document Analysis and Recognition (ICDAR), pages 461–465. IEEE Computer Society, 2007. doi:10.1109/ICDAR.2007.4378752.

50 Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In Thomas Lengauer, editor, Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, volume 726 of Lecture Notes in Computer Science, pages 372–383. Springer, 1993. doi:10.1007/3-540-57273-2_72.

51 Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk. Global curve simplification. In Proc. 27th Annual European Symposium on Algorithms (ESA), volume 144 of LIPIcs, pages 67:1–67:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ESA.2019.67.

52 Thijs van der Horst and Tim Ophelders. Faster Fréchet distance approximation through truncated smoothing. In Proc. 40th International Symposium on Computational Geometry (SoCG), volume 293 of LIPIcs, pages 63:1–63:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.63.

53 Thijs van der Horst, Marc J. van Kreveld, Tim Ophelders, and Bettina Speckmann. A subquadratic $n^e$-approximation for the continuous Fréchet distance. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1759–1776. SIAM, 2023. doi:10.1137/1.9781611977554.CH67.
54 Marc J. van Kreveld, Maarten Löffler, and Lionov Wiratma. On optimal polyline simplification using the Hausdorff and Fréchet distance. *J. Comput. Geom.*, 11(1):1–25, 2020. doi:10.20382/JO CG.V11I1A1.

55 Remco C. Veltkamp. Shape matching: Similarity measures and algorithms. In *Proc. International Conference on Shape Modeling and Applications (SMI)*, page 188. IEEE Computer Society, 2001. doi:10.1109/SMA.2001.923389.

56 Carola Wenk. *Shape Matching in Higher Dimensions*. PhD thesis, Free University Berlin, 2003. doi:10.17169/refubium-8310.