Exact algorithms for partial curve matching via the Fréchet distance

Abstract

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 curves, we wish to maximize the total length of subcurves that are close to each other, where closeness is measured by the Frechet distance, a common distance measure for curves. The resulting maximal length is called the partial Frechet similarity between the two input curves.Given two polygonal curves P and Q in Rd of size m and n, respectively, we present the first exact algorithm that runs in polynomial time to compute fδ(P, Q), the partial Frechet similarity between P and Q, under the L1 and L∞ norms. Specifically, we formulate the problem of computing fδ(P, Q) as a longest path problem, and solve it in O(mn(m + n) log(mn)) time, under the L1 or L∞ norm, using a shortest-path map type decomposition. To the best of our knowledge, this is the first paper to study this natural definition of partial curve similarity in the continuous setting (with all points in the curve considered), and present a polynomial-time exact algorithm for it.