The Fréchet distance is a well-studied and very popular measure of similarity of two curves.
Many variants and extensions have been studied since Alt and Godau introduced this …

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 …

Given two simplicial complexes in Rd and start and end vertices in each complex, we show
how to compute curves (in each complex) between these vertices, such that the weak …

Curve matching is a fundamental problem that occurs in many applications. In this paper, we
study the problem of measuring partial similarity between curves. Specifically, given two …

The Fréchet distance between two curves in the plane is the minimum length of a leash that
allows a dog and its owner to walk along their respective curves, from one end to the other …

Given two polygonal curves in the plane, there are many ways to define a notion of similarity
between them. One popular measure is the Fréchet distance. Since it was proposed by Alt …

A noticeable fraction of Algorithms papers in the last few decades improve the running time
of well-known algorithms for fundamental problems by logarithmic factors. For example, the …

We show by reduction from the Orthogonal Vectors problem that algorithms with strongly
subquadratic running time cannot approximate the Fréchet distance between curves better …

Given two polygonal curves in the plane, there are many ways to define a notion of similarity
between them. One measure that is extremely popular is the Fréchet distance. Since it has …

In this paper, we introduce a new generalization of the well-known Fréchet distance
between two polygonal curves, and provide an efficient algorithm for computing it. The …