2013/06/12 by Wouter Meulemans, Meulemans, Wouter · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Data Management and Algorithms #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1306.2827
arxiv created 2013/06/12 · openalex publication_date 2013/06/12 · arxiv updated 2013/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a map matching problem, the task of finding in an embedded graph a path that has low distance to a given curve in R2. The Fréchet distance is a common measure for this problem. Efficient methods exist to compute the best path according to this measure. However, these methods cannot guarantee that the result is simple (i.e. it does not intersect itself) even if the given curve is simple. In this paper, we prove that it is in fact NP-complete to determine the existence a simple cycle in a planar straight-line embedding of a graph that has at most a given Fréchet distance to a given simple closed curve. We also consider the implications of our proof on some variants of the problem.