TU/e Research Portal (Eindhoven University of Technology) · 2009 · 70 citations · 21 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryData StructuresApproximation AlgorithmsMetric GeometryCurve MatchingExact AlgorithmsGeometric MatchingMatching AlgorithmsPolynomial Time ComplexityPolynomial-time AlgorithmsShape MatchingSimilarity Detection
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.
21
On map-matching vehicle tracking data
Sotiris Brakatsoulas, Dieter Pfoser, Rocio Zozaya Salas et al. · 2005 · 507 citations
Computing, Geoinformatics, Global Navigation Satellite Systems +13
Helmut Alt, Alon Efrat, Günter Rote et al. · Journal of Algorithms · 2003 · 183 citations