In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of k base curves of length at most l such that the sum of Fréchet distances of the time series to a "Fréchet combination" of the base curves is minimized. Here, a Fréchet combination allows to combine individually scaled base curves using a k-dimensional traversal. We call the problem of finding a set of optimal base curves the Fréchet decomposition problem and we consider two variants: (a) the base curves can be arbitrary curves of bounded length and (b) the curves come from a given finite set of candidate curves. We think of the Fréchet decomposition problem as a Fréchet variant of principal component analysis. For the case of a single base curve we develop a (1+ε)-approximation algorithm for the Fréchet decomposition problem. Additionally we give an exact algorithm for the projection distance problem that asks to compute the distance of one given time series to a given set of k base curves. This allows us to design an exact algorithm for the Fréchet decomposition problem for general k when curves come from a fixed candidate set.

In the metric k-median problem we are given a finite metric space (X∪ Y, 𝐝) and the objective is to compute a set of k centers C ⊆ Y that minimizes ∑_{p ∈ X} min_{c ∈ C} 𝐝(p,c). In general metric spaces, the best polynomial time algorithm, which is due to Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson [Vincent Cohen-Addad et al., 2025], computes a (2+ε)-approximation for arbitrary constant ε > 0. However, if the metric space has bounded doubling dimension, a near linear time (1+ε)-approximation algorithm is known due to the work of Cohen-Addad, Feldmann, and Saulpic [Vincent Cohen{-}Addad et al., 2021]. In this paper, we show that the (1+ε)-approximation algorithm can be generalized to the case when either X or Y has bounded doubling dimension (but the other set not). The case when X has bounded doubling dimension is motivated by the assumption that even though X is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when Y has bounded doubling dimension is perhaps more natural. It is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the (k,𝓁)-median problem under discrete Fréchet distance when 𝓁 is constant. The latter problem is a version of the k-median problem under Fréchet distance when the input consists of time series of z reals and where the centers are time series of 𝓁 reals [Anne Driemel et al., 2016]. Previously, for this problem no (1+ε)-approximation algorithm with running time polynomial in k was known. We also introduce a novel complexity reduction for time series of real values that leads to a similar result for the case of discrete Fréchet distance. In order to solve the case when Y has a bounded doubling dimension, we introduce a form of dimension reduction that replaces points from X by sets of points in Y. To solve the case when X has a bounded doubling dimension, we generalize Talwar’s decomposition [Kunal Talwar, 2004] of doubling metrics to our setting. The running time of our algorithms is 2^{2^t} Õ(n+m) where t = O(ddim log ddim/ε) and where ddim is the doubling dimension of X (resp. Y). The results also extend to the metric (uncapacitated) facility location problem. We believe that our techniques are likely applicable to other problems.

The Fréchet distance is a computational mainstay for comparing polygonal curves. The Fréchet distance under translation, which is a translation invariant version, considers the similarity of two curves independent of their location in space. It is defined as the minimum Fréchet distance that arises from allowing arbitrary translations of the input curves. This problem and numerous variants of the Fréchet distance under some transformations have been studied, with more work concentrating on the discrete Fréchet distance, leaving a significant gap between the discrete and continuous versions of the Fréchet distance under transformations. Our contribution is twofold: First, we present an algorithm for the Fréchet distance under translation on 1-dimensional curves of complexity n with a running time of $\mathcal{O}(n^{8/3} log^3 n)$. To achieve this, we develop a novel framework for the problem for 1-dimensional curves, which also applies to other scenarios and leads to our second contribution. We present an algorithm with the same running time of $\mathcal{O}(n^{8/3} \log^3 n)$ for the Fréchet distance under scaling for 1-dimensional curves. For both algorithms we match the running times of the discrete case and improve the previously best known bounds of $\tilde{\mathcal{O}}(n^4)$. Our algorithms rely on technical insights but are conceptually simple, essentially reducing the continuous problem to the discrete case across different length scales.

In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size $n$ in a discrete space $[Δ]^d$, where queries can be made to an oracle that responds to orthogonal range counting requests. The query complexity of an optimization problem is measured by the number of oracle queries required to compute an estimator for the problem. We investigate two problems in this framework, the Euclidean Minimum Spanning Tree (MST) and Earth Mover Distance (EMD). For EMD, we show the existence of an estimator that approximates the cost of EMD with $O(\log Δ)$-relative error and $O(\frac{nΔ}{s^{1+1/d}})$-additive error using $O(s\polylog Δ)$ range counting queries for any parameter $s$ with $1\leq s \leq n$. Moreover, we prove that this bound is tight. For MST, we demonstrate that the weight of MST can be estimated within a factor of $(1 \pm \eps)$ using $\tilde{O}(\sqrt{n})$ range counting queries.

We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is given access to the input curves via a query oracle: a query returns the set of vertices of the curve that lie within a radius δ of a specified vertex of the other curve. The goal is to use a small number of queries to determine with constant probability whether the two curves are similar (i.e., their discrete Fréchet distance is at most δ) or they are "ε-far" (for 0 < ε < 2) from being similar, i.e., more than an ε-fraction of the two curves must be ignored for them to become similar. We present two algorithms which are sublinear assuming that the curves are t-approximate shortest paths in the ambient metric space, for some t ≪ n. The first algorithm uses O(t/ε log t/ε) queries and is given the value of t in advance. The second algorithm does not have explicit knowledge of the value of t and therefore needs to gain implicit knowledge of the straightness of the input curves through its queries. We show that the discrete Fréchet distance can still be tested using roughly O({t³+t² log n}/ε) queries ignoring logarithmic factors in t. Our algorithms work in a matrix representation of the input and may be of independent interest to matrix testing. Our algorithms use a mild uniform sampling condition that constrains the edge lengths of the curves, similar to a polynomially bounded aspect ratio. Applied to testing the continuous Fréchet distance of t-straight curves, our algorithms can be used for (1+ε')-approximate testing using essentially the same bounds as stated above with an additional factor of poly(1/(ε')).

Many application areas collect unstructured trajectory data. In subtrajectory clustering, one is interested to find patterns in this data using a hybrid combination of segmentation and clustering. We analyze two variants of this problem based on the well-known SetCover and CoverageMaximization problems. In both variants the set system is induced by metric balls under the Fréchet distance centered at polygonal curves. Our algorithms focus on improving the running time of the update step of the generic greedy algorithm by means of a careful combination of sweeps through a candidate space. In the first variant, we are given a polygonal curve P of complexity n, distance threshold Δ and complexity bound 𝓁 and the goal is to identify a minimum-size set of center curves 𝒞, where each center curve is of complexity at most 𝓁 and every point p on P is covered. A point p on P is covered if it is part of a subtrajectory π_p of P such that there is a center c ∈ 𝒞 whose Fréchet distance to π_p is at most Δ. We present an approximation algorithm for this problem with a running time of 𝒪((n²𝓁 + √{k_Δ}n^{5/2})log²n), where k_Δ is the size of an optimal solution. The algorithm gives a bicriterial approximation guarantee that relaxes the Fréchet distance threshold by a constant factor and the size of the solution by a factor of 𝒪(log n). The second problem variant asks for the maximum fraction of the input curve P that can be covered using k center curves, where k ≤ n is a parameter to the algorithm. For the second problem variant, our techniques lead to an algorithm with a running time of 𝒪((k+𝓁)n²log²n) and similar approximation guarantees. Note that in both algorithms k,k_Δ ∈ O(n) and hence the running time is cubic, or better if k ≪ n.

Abstract The DTW Barycenter Averaging (DBA) algorithm is a widely used algorithm for estimating the mean of a given set of point sequences. In this context, the mean is defined as a point sequence that minimises the sum of dynamic time warping distances (DTW). The algorithm is similar to the k-means algorithm in the sense that it alternately repeats two steps: (1) computing an optimal assignment to the points of the current mean, and (2) computing an optimal mean under the current assignment. The popularity of DBA can be attributed to the fact that it works well in practice, despite any theoretical guarantees to be known. In our paper, we aim to initiate a theoretical study of the number of iterations that DBA performs until convergence. We assume the algorithm is given n sequences of m points in $${\mathbb R}^d$$ and a parameter k that specifies the length of the mean sequence to be computed. We show that, in contrast to its fast running time in practice, the number of iterations can be exponential in k in the worst case — even if the number of input sequences is $$n=2$$ . We complement these findings with experiments on real-world data that suggest this worst-case behaviour is likely degenerate. To better understand the performance of the algorithm on non-degenerate input, we study DBA in the model of smoothed analysis, upper-bounding the expected number of iterations in the worst case under random perturbations of the input. Our smoothed upper bound is $$ \widetilde{O} \left( n^2 m^{8\frac{n}{d}+6}d^4k^6\sigma ^{-2} \right) $$ , where $$\sigma $$ is the variance of the perturbation and the $$\widetilde{O}(\cdot )$$ -notation omits logarithmic factors. For our analysis, we adapt the set of techniques that were developed for analysing the k-means method and observe that this set of techniques is not sufficient to obtain tight bounds for general n.

User interfaces for inspecting spatio-temporal events often allow their users to filter the events by specifying a time window with a time slider. We consider the case that filtered events are visualized on a map using textual or iconic labels. However, to ensure a clear visualization, not all filtered events are annotated with a label. We present algorithms for setting up a data structure that encodes for every possible time window the set of displayed labels. Our algorithms ensure that the displayed labels never overlap and guarantee the stability of the labeling during certain basic interactions with the time slider. Assuming that the labels have different priorities (weights), we aim to maximize the weight of the displayed labels integrated over all possible time windows. As basic interactions, we consider moving the entire time window, symmetrically scaling it, and dragging one of its endpoints. We consider two stability requirements: (1) during a basic interaction, a label should appear and disappear at most once; (2) if a label is displayed for a time window $Q$Q, then it is also displayed for all the time windows contained in $Q$Q and that contain its timestamp. We prove that finding an optimal solution is NP-hard and propose efficient constant-factor approximation algorithms for unit-square and unit-disk labels, as well as a fast greedy heuristic for arbitrarily shaped labels. In experiments on real-world data, we compare the non-exact algorithms with an exact approach through integer linear programming.

The fine-grained complexity of computing the Fréchet distance has been a topic of much recent work, starting with the quadratic SETH-based conditional lower bound by Bringmann from 2014. Subsequent work established largely the same complexity lower bounds for the Fréchet distance in 1D. However, the imbalanced case, which was shown by Bringmann to be tight in dimensions $d\geq 2$, was still left open. Filling in this gap, we show that a faster algorithm for the Fréchet distance in the imbalanced case is possible: Given two 1-dimensional curves of complexity $n$ and $n^α$ for some $α\in (0,1)$, we can compute their Fréchet distance in $O(n^{2α} \log^2 n + n \log n)$ time. This rules out a conditional lower bound of the form $O((nm)^{1-ε})$ that Bringmann showed for $d \geq 2$ and any $\varepsilon>0$ in turn showing a strict separation with the setting $d=1$. At the heart of our approach lies a data structure that stores a 1-dimensional curve $P$ of complexity $n$, and supports queries with a curve $Q$ of complexity~$m$ for the continuous Fréchet distance between $P$ and $Q$. The data structure has size in $\mathcal{O}(n\log n)$ and uses query time in $\mathcal{O}(m^2 \log^2 n)$. Our proof uses a key lemma that is based on the concept of visiting orders and may be of independent interest. We demonstrate this by substantially simplifying the correctness proof of a clustering algorithm by Driemel, Krivošija and Sohler from 2015.

The DTW Barycenter Averaging (DBA) algorithm is a widely used algorithm for estimating the mean of a given set of point sequences. In this context, the mean is defined as a point sequence that minimises the sum of dynamic time warping distances (DTW). The algorithm is similar to the k-means algorithm in the sense that it alternately repeats two steps: (1) computing an optimal assignment to the points of the current mean, and (2) computing an optimal mean under the current assignment. The popularity of DBA can be attributed to the fact that it works well in practice, despite any theoretical guarantees to be known. In our paper, we aim to initiate a theoretical study of the number of iterations that DBA performs until convergence. We assume the algorithm is given n sequences of m points in ℝd and a parameter k that specifies the length of the mean sequence to be computed. We show that, in contrast to its fast running time in practice, the number of iterations can be exponential in k in the worst case — even if the number of input sequences is n = 2. We complement these findings with experiments on real-world data that suggest this worst-case behaviour is likely degenerate. To better understand the performance of the algorithm on non-degenerate input, we study DBA in the model of smoothed analysis, upper-bounding the expected number of iterations in the worst case under random perturbations of the input. Our smoothed upper bound is polynomial in k, n and d, and for constant n, it is also polynomial in m. For our analysis, we adapt the set of techniques that were developed for analysing k-means and observe that this set of techniques is not sufficient to obtain tight bounds for general n.

The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min–max formulation that considers all orientation-preserving bijective mappings between the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterised version of this problem, where the number of shortcuts is bounded by a parameter \(k\) . The corresponding decision problem can be stated as follows: Given two polygonal curves \(T\) and \(B\) of at most \(n\) vertices, a parameter \(k\) and a distance threshold \(\delta\) , is it possible to introduce \(k\) shortcuts along \(B\) such that the Fréchet distance of the resulting curve and the curve \(T\) is at most \(\delta\) ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (1) there exists a decision algorithm with running time in \(\mathcal{O}(kn^{2k+2}\log n)\) ; (2) assuming the exponential-time hypothesis (ETH), there exists no algorithm with running time bounded by \(n^{o(k)}\) . In contrast, we also show that efficient approximate decider algorithms are possible, even when \(k\) is large. We present a \((3+\varepsilon)\) -approximate decider algorithm with running time in \(\mathcal{O}(kn^{2}\log^{2}n)\) for fixed \(\varepsilon\) . In addition, we can show that, if \(k\) is a constant and the two curves are \(c\) -packed for some constant \(c\) , then the approximate decider algorithm runs in near-linear time.

For the best human-robot interaction experience, the robot's navigation policy should take into account personal preferences of the user. In this paper, we present a learning framework complemented by a perception pipeline to train a depth vision-based, personalized navigation controller from user demonstrations. Our virtual reality interface enables the demonstration of robot navigation trajectories under motion of the user for dynamic interaction scenarios. The novel perception pipeline enrolls a variational autoencoder in combination with a motion predictor. It compresses the perceived depth images to a latent state representation to enable efficient reasoning of the learning agent about the robot's dynamic environment. In a detailed analysis and ablation study, we evaluate different configurations of the perception pipeline. To further quantify the navigation controller's quality of personalization, we develop and apply a novel metric to measure preference reflection based on the Frechet Distance. We discuss the robot's navigation performance in various virtual scenes and demonstrate the first personalized robot navigation controller that solely relies on depth images. A supplemental video highlighting our approach is available online11Full video: hrl.uni-bonn.de/publications/deheuve123iros_learning.mp4.

In 2015, Driemel, Krivošija, and Sohler introduced the k,ℓ -median clustering problem for polygonal curves under the Fréchet distance. Given a set of input curves, the problem asks to find k median curves of at most ℓ vertices each that minimize the sum of Fréchet distances over all input curves to their closest median curve. A major shortcoming of their algorithm is that the input curves are restricted to lie on the real line. In this article, we present a randomized bicriteria-approximation algorithm that works for polygonal curves in ℝ d and achieves approximation factor (1+ɛ) with respect to the clustering costs. The algorithm has worst-case running time linear in the number of curves, polynomial in the maximum number of vertices per curve (i.e., their complexity), and exponential in d , ℓ, 1/ɛ and 1/δ (i.e., the failure probability). We achieve this result through a shortcutting lemma, which guarantees the existence of a polygonal curve with similar cost as an optimal median curve of complexity ℓ, but of complexity at most 2ℓ -2, and whose vertices can be computed efficiently. We combine this lemma with the superset sampling technique by Kumar et al. to derive our clustering result. In doing so, we describe and analyze a generalization of the algorithm by Ackermann et al., which may be of independent interest.

The Fréchet distance is a well-studied similarity measure between curves that is widely used throughout computer science. Motivated by applications where curves stem from paths and walks on an underlying graph (such as a road network), we define and study the Fréchet distance for paths and walks on graphs. When provided with a distance oracle of G with O(1) query time, the classical quadratic-time dynamic program can compute the Fréchet distance between two walks P and Q in a graph G in O(|P|⋅|Q|) time. We show that there are situations where the graph structure helps with computing Fréchet distance: when the graph G is planar, we apply existing (approximate) distance oracles to compute a (1+ε)-approximation of the Fréchet distance between any shortest path P and any walk Q in O(|G|log|G|/√ε+|P|+|Q|/ε) time. We generalise this result to near-shortest paths, i.e. κ-straight paths, as we show how to compute a (1+ε)-approximation between a κ-straight path P and any walk Q in O(|G|log|G|/√ε+|P|+(κ|Q|)/ε) time. Our algorithmic results hold for both the strong and the weak discrete Fréchet distance over the shortest path metric in G. Finally, we show that additional assumptions on the input, such as our assumption on path straightness, are indeed necessary to obtain truly subquadratic running time. We provide a conditional lower bound showing that the Fréchet distance, or even its 1.01-approximation, between arbitrary paths in a weighted planar graph cannot be computed in O((|P|⋅|Q|)^{1-δ}) time for any δ > 0 unless the Orthogonal Vector Hypothesis fails. For walks, this lower bound holds even when G is planar, unit-weight and has O(1) vertices.

Subtrajectory clustering is an important variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number $k$ of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given $Δ$ to a representative curve. We focus on the case where the representative curves are line segments and approach this NP-hard problem with classical techniques from the area of geometric set cover: we use a variant of the multiplicative weights update method which was first suggested by Brönniman and Goodrich for set cover instances with small VC-dimension. We obtain a bicriteria-approximation algorithm that computes a set of $O(k\log(k))$ line segments that cover a given polygonal curve of $n$ vertices under Fréchet distance at most $O(Δ)$. We show that the algorithm runs in $\widetilde{O}(k^2 n + k n^3)$ time in expectation and uses $ \widetilde{O}(k n + n^3)$ space. For two dimensional input curves that are $c$-packed, we bound the expected running time by $\widetilde{O}(k^2 c^2 n)$ and the space by $ \widetilde{O}(kn + c^2 n)$. In $\mathbb{R}^d$ the dependency on $n$ instead is quadratic. In addition, we present a variant of the algorithm that uses implicit weight updates on the candidate set and thereby achieves near-linear running time in $n$ without any assumptions on the input curve, while keeping the same approximation bounds. This comes at the expense of a small (polylogarithmic) dependency on the relative arclength.

The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijections of the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterized version of this problem, where the number of shortcuts is bounded by a parameter $k$. The corresponding decision problem can be stated as follows: Given two polygonal curves $T$ and $B$ of at most $n$ vertices, a parameter $k$ and a distance threshold $δ$, is it possible to introduce $k$ shortcuts along $B$ such that the Fréchet distance of the resulting curve and the curve $T$ is at most $δ$? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (i) assuming the exponential-time-hypothesis (ETH), there exists no algorithm with running time bounded by $n^{o(k)}$; (ii) there exists a decision algorithm with running time in $O(kn^{2k+2}\log n)$. In contrast, we also show that efficient approximate decider algorithms are possible, even when $k$ is large. We present a $(3+\varepsilon)$-approximate decider algorithm with running time in $O(k n^2 \log^2 n)$ for fixed $\varepsilon$. In addition, we can show that, if $k$ is a constant and the two curves are $c$-packed for some constant $c$, then the approximate decider algorithm runs in near-linear time.

We study the c-approximate near neighbor problem under the continuous Fréchet distance: Given a set of n polygonal curves with m vertices, a radius δ > 0, and a parameter k ≤ m, we want to preprocess the curves into a data structure that, given a query curve q with k vertices, either returns an input curve with Fréchet distance at most c · δ to q, or returns that there exists no input curve with Fréchet distance at most δ to q. We focus on the case where the input and the queries are one-dimensional polygonal curves—also called time series—and we give a comprehensive analysis for this case. We obtain new upper bounds that provide different tradeoffs between approximation factor, preprocessing time, and query time. Our data structures improve upon the state of the art in several ways. We show that for any 0 < ∊ ≤ 1 an approximation factor of (1 + ∊) can be achieved within the same asymptotic time bounds as the previously best result for (2 + ∊). Moreover, we show that an approximation factor of (2 + ∊) can be obtained by using preprocessing time and space O(nm), which is linear in the input size, and query time in , where the previously best result used preprocessing time in and query time in O(1)k. We complement our upper bounds with matching conditional lower bounds based on the Orthogonal Vectors Hypothesis. Interestingly, some of our lower bounds already hold for any super-constant value of k. This is achieved by proving hardness of a one-sided sparse version of the Orthogonal Vectors problem as an intermediate problem, which we believe to be of independent interest.

No abstract available.

In 2015, Driemel, Krivošija and Sohler introduced the (k, ℓ)-median problem for clustering polygonal curves under the Fréchet distance. Given a set of input curves, the problem asks to find k median curves of at most ℓ vertices each that minimize the sum of Fréchet distances over all input curves to their closest median curve. A major shortcoming of their algorithm is that the input curves are restricted to lie on the real line. In this paper, we present a randomized bicriteria-approximation algorithm that works for polygonal curves in ℝd and achieves approximation factor (1 + ∊) with respect to the clustering costs. The algorithm has worst-case running-time linear in the number of curves, polynomial in the maximum number of vertices per curve, i.e. their complexity, and exponential in d, ℓ, ∊ and δ, i.e., the failure probability. We achieve this result through a shortcutting lemma, which guarantees the existence of a polygonal curve with similar cost as an optimal median curve of complexity ℓ, but of complexity at most 2ℓ – 2, and whose vertices can be computed efficiently. We combine this lemma with the superset-sampling technique by Kumar et al. to derive our clustering result. In doing so, we describe and analyze a generalization of the algorithm by Ackermann et al., which may be of independent interest.

Abstract The Vapnik–Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computational tasks such as classification, range counting, and density estimation through the use of sampling bounds. We analyze set systems where the ground set X is a set of polygonal curves in $$\mathbb {R}^d$$ R d and the sets $$\mathcal {R}$$ R are metric balls defined by curve similarity metrics, such as the Fréchet distance and the Hausdorff distance, as well as their discrete counterparts. We derive upper and lower bounds on the VC dimension that imply useful sampling bounds in the setting that the number of curves is large, but the complexity of the individual curves is small. Our upper and lower bounds are either near-quadratic or near-linear in the complexity of the curves that define the ranges and they are logarithmic in the complexity of the curves that define the ground set.

Center-based clustering, in particular k-means clustering, is frequently used for point data. Its advantages include that the resulting clustering is often easy to interpret and that the cluster centers provide a compact representation of the data. Recent theoretical advances have been made in generalizing center-based clustering to trajectory data. Building upon these theoretical results, we present practical algorithms for center-based trajectory clustering.

The Euclidean k-Center problem is a classical problem that has been extensively studied in computer science. Given a set G of n points in Euclidean space, the problem is to determine a set C of k centers (not necessarily part of G) such that the maximum distance between a point in G and its nearest neighbor in C is minimized. In this paper we study the corresponding (k, ℓ)-CENTER problem for polygonal curves under the Fréchet distance, that is, given a set G of n polygonal curves in ℝd, each of complexity m, determine a set C of k polygonal curves in ℝd, each of complexity ℓ, such that the maximum Fréchet distance of a curve in G to its closest curve in C is minimized. In their 2016 paper, Driemel, Krivošija, and Sohler give a near-linear time (1 + ε-approximation algorithm for one-dimensional curves, assuming that k and ℓ are constants. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher. Our analysis thus extends to application-relevant input data such as GPS-trajectories and protein backbones. We show that, if ℓ is part of the input, then there is no polynomial-time approximation scheme unless P = NP. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet distance on two-dimensional curves, we show hardness of approximation within a factor close to 2.598. This result also holds when k = 1, and the NP-hardness extends to the case that ℓ = ∞, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet distance. Finally, we observe that a careful adaptation of Gonzalez’ algorithm in combination with a curve simplification yields a 3-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.

Modern tracking technology has made the collection of large numbers of densely sampled trajectories of moving objects widely available. We consider a fundamental problem encountered when analysing such data: Given n polygonal curves S in ℝd, preprocess S into a data structure that answers queries with a query curve q and radius ρ for the curves of S that have Fréchet distance at most ρ to q. We initiate a comprehensive analysis of the space/query-time tradeoff for this data structuring problem. Our lower bounds imply that any data structure in the pointer model model that achieves Q(n) + O(k) query time, where k is the output size, has to use roughly n((n/Q(n))2) space in the worst case, even if queries are mere points (for the discrete Fréchet distance) or line segments (for the continuous Fréchet distance). More importantly, we show that more complex queries and input curves lead to additional logarithmic factors in the lower bound. Roughly speaking, the number of logarithmic factors added is linear in the number of edges added to the query and input curve complexity. This means that the space/query time tradeoff worsens by an exponential factor of input and query complexity. This behaviour addresses an open question (see [1, 9]) in the range searching literature concerning multilevel partition trees which may be of independent interest, namely, whether it is possible to avoid the additional logarithmic factors in the space and query time of a multilevel partition tree. We answer this question negatively. On the positive side, we show we can build data structures for the Fréchet distance by using semialgebraic range searching. The space/query-time tradeoff of our data structure for the discrete Fréchet distance is in line with the lower bound, as the number of levels in the data structure is O(t), where t denotes the maximal number of vertices of a curve. For the continuous Fréchet distance, the number of levels increases to O(t2).

We study data structures for storing a set of polygonal curves in R^d such that, given a query curve, we can efficiently retrieve similar curves from the set, where similarity is measured using the discrete Fréchet distance or the dynamic time warping distance. To this end we devise the first locality-sensitive hashing schemes for these distance measures. A major challenge is posed by the fact that these distance measures internally optimize the alignment between the curves. We give solutions for different types of alignments including constrained and unconstrained versions. For unconstrained alignments, we improve over a result by Indyk [SoCG 2002] for short curves. Let n be the number of input curves and let m be the maximum complexity of a curve in the input. In the particular case where m <= (a/(4d)) log n, for some fixed a>0, our solutions imply an approximate near-neighbor data structure for the discrete Fréchet distance that uses space in O(n^(1+a) log n) and achieves query time in O(n^a log^2 n) and constant approximation factor. Furthermore, our solutions provide a trade-off between approximation quality and computational performance: for any parameter k in [m], we can give a data structure that uses space in O(2^(2k) m^(k-1) n log n + nm), answers queries in O( 2^(2k) m^(k) log n) time and achieves approximation factor in O(m/k).

The Fréchet distance is a popular distance measure for curves. We study the problem of clustering time series under the Fréchet distance. In particular, we give (1 + ∊)-approximation algorithms for variations of the following problem with parameters k and ℓ. Given n univariate time series P, each of complexity at most m, we find k time series, not necessarily from P, which we call cluster centers and which each have complexity at most ℓ, such that (a) the maximum distance of an element of P to its nearest cluster center or (b) the sum of these distances is minimized. Our algorithms have running time near-linear in the input size for constant ∊, k and ℓ. To the best of our knowledge, our algorithms are the first clustering algorithms for the Fréchet distance which achieve an approximation factor of (1 + ∊) or better.

In the trajectory segmentation problem, we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to be solvable efficiently for monotone criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment. To the best of our knowledge, no theoretical results are known for nonmonotone criteria. We present a broader study of the segmentation problem, and suggest a general framework for solving it, based on the start-stop diagram : a 2-dimensional diagram that represents all valid and invalid segments of a given trajectory. This yields two subproblems: (1) computing the start-stop diagram, and (2) finding the optimal segmentation for a given diagram. We show that (2) is NP-hard in general. However, we identify properties of the start-stop diagram that make the problem tractable and give a polynomial-time algorithm for this case. We study two concrete nonmonotone criteria that arise in practical applications in more detail. Both are based on a given univariate attribute function f over the domain of the trajectory. We say a segment satisfies an outlier-tolerant criterion if the value of f lies within a certain range for at least a given percentage of the length of the segment. We say a segment satisfies a standard deviation criterion if the standard deviation of f over the length of the segment lies below a given threshold. We show that both criteria satisfy the properties that make the segmentation problem tractable. In particular, we compute an optimal segmentation of a trajectory based on the outlier-tolerant criterion in O ( n 2 log n + kn 2 ) time and on the standard deviation criterion in O ( kn 2 ) time, where n is the number of vertices of the input trajectory and k is the number of segments in an optimal solution.

We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [2008] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is Θ( n + m √ n ) in the worst case, where n denotes the number of triangles that define the terrain and m denotes the number of Voronoi sites. We prove that, under a relaxed set of assumptions, the Voronoi diagram has expected complexity O ( n + m ), given that the sites are sampled uniformly at random from the domain of the terrain (or the surface of the terrain). Furthermore, we present a construction of a terrain that implies a lower bound of Ω( nm 2/3 ) on the expected worst-case complexity if these assumptions on the terrain are dropped. As an additional result, we show that the expected fatness of a cell in a random planar Voronoi diagram is bounded by a constant.

We study the shortcut Fréchet distance, a natural variant of the Fréchet distance, that allows us to take shortcuts from and to any point along one of the curves. The classic Fréchet distance is a bottle-neck distance measure and hence quite sensitive to outliers. The shortcut Fréchet distance allows us to cut across outliers and hence produces more meaningful results when dealing with real world data. Driemel and Har-Peled recently described approximation algorithms for the restricted case where shortcuts have to start and end at input vertices. We show that, in the general case, the problem of computing the shortcut Fréchet distance is NP-hard. This is the first hardness result for a variant of the Fréchet distance between two polygonal curves in the plane. We also present two algorithms for the decision problem: a 3-approximation algorithm for the general case and an exact algorithm for the vertex-restricted case. Both algorithms run in O(n3 log n) time.

In the trajectory segmentation problem we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to be solvable efficiently for monotone criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment [4]. To the best of our knowledge, no theoretical results are known for non-monotone criteria. We present a broader study of the segmentation problem, and suggest a general framework for solving it, based on the start-stop diagram: a 2-dimensional diagram that represents all valid and invalid segments of a given trajectory. This yields two subproblems: (i) computing the start-stop diagram, and (ii) finding the optimal segmentation for a given diagram. We show that (ii) is NP-hard in general. However, we identify properties of the start-stop diagram that make the problem tractable, and give polynomial-time algorithm for this case. We study two concrete non-monotone criteria that arise in practical applications in more detail. Both are based on a given univariate attribute function f over the domain of the trajectory. We say a segment satisfies an outlier-tolerant criterion if the value of f lies within a certain range for at least a given percentage of the length of the segment. We say a segment satisfies a standard deviation criterion if the standard deviation of f over the length of the segment lies below a given threshold. We show that both criteria satisfy the properties that make the segmentation problem tractable. In particular, we compute an optimal segmentation of a trajectory based on the outlier-tolerant criterion in O(n2 log n+kn2) time, and on the standard deviation criterion in O(kn2) time, where n is the number of vertices of the input trajectory and k is the number of segments in an optimal solution.

The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a $(3+\varepsilon)$-approximation to the minimum Fréchet distance over all possible such shortcuts, in near linear time, if the curve is $c$-packed and the number of shortcuts is either small or unbounded. To facilitate the new algorithm we develop several new tools: (a) a data structure for preprocessing a curve (not necessarily $c$-packed) that supports $(1+\varepsilon)$-approximate Fréchet distance queries between a subcurve (of the original curve) and a line segment; (b) a near linear time algorithm that computes a permutation of the vertices of a curve, such that any prefix of $2k-1$ vertices of this permutation forms an optimal approximation (up to a constant factor) to the original curve compared to any polygonal curve with $k$ vertices, for any $k > 0$; and (c) a data structure for preprocessing a curve that supports approximate Fréchet distance queries between a subcurve and query polygonal curve. The query time depends quadratically on the complexity of the query curve and only (roughly) logarithmically on the complexity of the original curve. To our knowledge, these are the first data structures to support these kind of queries efficiently.

We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et.al. [abt-cbvdrt-08] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is Θ(n + m √n) in the worst case, where n denotes the number of triangles that define the terrain and m denotes the number of Voronoi sites. We prove that under a relaxed set of assumptions the Voronoi diagram has expected complexity O(n+m), given that the sites have a uniform distribution on the domain of the terrain (or the surface of the terrain). Furthermore, we present a worst-case construction of a terrain which implies a lower bound of Ω(n m2/3) on the expected worst-case complexity if these assumptions on the terrain are dropped.

The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a constant factor approximation to the minimum Fréchet distance over all possible such shortcuts. Our algorithm runs in O(c2 kn log3 n) time if one is allowed to take at most k shortcuts and the input curves are c-packed. For the case where the number of shortcuts is unrestricted, we describe an algorithm which runs in O(c2 n log3 n) time. To facilitate the new algorithm we develop several new data-structures, which we believe to be of independent interest: (i) for range reporting on a curve, and (ii) for preprocessing a curve to answer queries for the Fréchet distance between a subcurve and a line segment.

We extend recent results using curve simplification for approximating the Fréchet distance of realistic curves in near linear time to map matching: the problem of matching a curve in an embedded graph.We show that the theoretical bounds on the running time of the previous result still hold if only one of the curves is simplified during the course of the approximation algorithm.This enables our extension to the case of map matching under the assumption that the graph is φ-low density for a constant φ.We present experimental evidence for this assumption and implement the extended approximate matching algorithm.We show that it performs well on real world data, such as GPS traces and road networks of urban areas.In particular, it is able to perform matching tasks that took several hours with the exact matching algorithm in under a second.

We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between polygonal curves. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and show similar results for other input models, such as low density.

In this paper we address the problem of segmenting a trajectory such that each segment is in some sense homogeneous. We formally define different spatio-temporal criteria under which a trajectory can be homogeneous, including location, heading, speed, velocity, curvature, sinuosity, and curviness. We present a framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria. In this framework, the segmentation problem can generally be solved in O(n log n) time, where n is the number of edges of the trajectory to be segmented.