Matching Curves to Imprecise Point Sets using Fréchet Distance

Original · EN

Let P be a polygonal curve in Rᵈ of length n, and S be a point-set of size k. The Curve/Point Set Matching problem consists of finding a polygonal curve Q on S such that the Fréchet distance from P is less than a given ε. We consider eight variations of the problem based on the distance metric used and the omittability or repeatability of the points. We provide closure to a recent series of complexity results for the case where S consists of precise points. More importantly, we formulate a more realistic version of the problem that takes into account measurement errors. This new problem is posed as the matching of a given curve to a set of imprecise points. We prove that all three variations of the problem that are in P when S consists of precise points become NP-complete when S consists of imprecise points. We also discuss approximation results.