Hardness Results on Curve/Point Set Matching with Fréchet Distance

Abstract

Let P be a polygonal curve in R^d of length n, and S be a point-set of size k. We consider the problem of finding a polygonal curve Q on S such that all points in S are visited and the Fréchet distance from $P$ is less than a given epsilon. We show that this problem is NP-complete, regardless of whether or not points from S are allowed be visited more than once. However, we also show that if the problem instance satisfies certain restrictions, the problem is polynomial-time solvable, and we briefly outline an algorithm that computes Q.