%0 Journal Article
%T Hardness Results on Curve/Point Set Matching with Fr¨¦chet Distance
%A Paul Accisano
%A Alper ¨¹ng£¿r
%J Computer Science
%D 2012
%I arXiv
%X 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\'echet 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.
%U http://arxiv.org/abs/1211.2030v1