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

2012/11/09 by Accisano, Paul, Üngör, Alper
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1211.2030

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.

Related

• Matching Curves to Imprecise Point Sets using Fréchet Distance
• Finding a Curve in a Point Set
• Solving Fréchet Distance Problems by Algebraic Geometric Methods
• The k-Fréchet distance
• Applied Similarity Problems Using Frechet Distance