Search

The Fréchet distance is a well studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown to be optimal assuming the Strong Exponential Time Hypothesis (SETH) [Bringmann, FOCS'14]. To overcome the worst-case quadratic time barrier, restricted classes of curves have been studied that attempt to capture realistic input curves. The most popular such class are -packed curves, for which the Fréchet distance has a -approximation in time [Driemel et al., DCG'12]. In dimension this cannot be improved to for any unless SETH fails [Bringmann, FOCS'14]. In this paper, exploiting properties that prevent stronger lower bounds, we present an improved algorithm with time complexity . This improves upon the algorithm by Driemel et al. for any . Moreover, our algorithm's dependence on , and is optimal in high dimensions apart from lower order factors, unless SETH fails. Our main new ingredients are as follows: For filling the classical free-space diagram we project short subcurves onto a line, which yields one-dimensional separated curves with roughly the same pairwise distances between vertices. Then we tackle this special case in near-linear time by carefully extending a greedy algorithm for the Fréchet distance of one-dimensional separated curves. [ABSTRACT FROM AUTHOR]

The article analyzes similarity of closed polygonal curves with respect to the Fréchet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm is described that determines whether the Fréchet distance between two closed polygonal curves with and vertices is less than a given number . The algorithm takes time whereas the previously known algorithms take time. [ABSTRACT FROM AUTHOR]

We study a modified version of the partial Fréchet similarity that is motivated by real world applications, e.g. the analysis of spectroscopic data in the context of astroinformatics and the analysis of birds' migration trajectories. In those practical applications of curve matching it is often necessary to ignore outliers while dissimilarities regarding individual directions should be weighted by individual costs. We enable both by computing the partial Fréchet similarity between polygonal curves w.r.t. a non-uniform metric. In particular, we measure distances by a function that is induced by a set of weighted vectors. We discuss the approximation quality of regarding any metric and present a polynomial time algorithm for computing an exact solution of the resulting modified partial Fréchet similarity. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2O(d2)m2n2log2(mn) the minimum Fréchet distance between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log3(mn) + (m2+n2)log (mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L∞ distance, we give an O(dmn (dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the maximum Fréchet distance, as well as the minimum and maximum Fréchet distance under translation. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size). [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of detecting commuting patterns in a trajectory. For this we search for similar subtrajectories. To measure spatial similarity we choose the Fréchet distance and the discrete Fréchet distance between subtrajectories, which are invariant under differences in speed. We give several approximation algorithms, and also show that the problem of finding the 'longest' subtrajectory cluster is as hard as MaxClique to compute and approximate. [ABSTRACT FROM AUTHOR]

Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known measure to characterize the similarity of two polygonal chains is the (continuous/discrete) Fréchet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in d-dimension under the discrete Fréchet distance. Given a set $\mathcal{C}$ of n polygonal chains in d-dimension, each with at most k vertices, we prove fundamental properties of such a Voronoi diagram $VD_F (\mathcal{C})$. Our main results are summarized as follows. • The combinatorial complexity of $VD_F (\mathcal{C})$ is at most O(ndk+∊). • The combinatorial complexity of $VD_F (\mathcal{C})$ is at least Ω(ndk) for dimension d = 1, 2; and Ω(nd(k-1)+2) for dimension d > 2. [ABSTRACT FROM AUTHOR]