@inproceedings{6148287b65b04c20ad177607e96676eb,
title = "Computing the Fr{\'e}chet distance between folded polygons",
abstract = "Computing the Fr{\'e}chet distance for surfaces is a surprisingly hard problem and the only known algorithm is limited to computing it between flat surfaces. We adapt this algorithm to create one for computing the Fr{\'e}chet distance for a class of non-flat surfaces which we call folded polygons. Unfortunately, the original algorithm cannot be extended directly. We present three different methods to adapt it. The first of which is a fixed-parameter tractable algorithm. The second is a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fr{\'e}chet distance in polynomial time.",
keywords = "Computational Geometry, Fr{\'e}chet Distance, Shape Matching",
author = "{Cook IV}, {Atlas F.} and Anne Driemel and Sariel Har-Peled and Jessica Sherette and Carola Wenk",
note = "Funding Information: ★ This work has been supported by the National Science Foundation grant NSF CA-REER CCF-0643597.; 12th International Symposium on Algorithms and Data Structures, WADS 2011 ; Conference date: 15-08-2011 Through 17-08-2011",
year = "2011",
doi = "10.1007/978-3-642-22300-6_23",
language = "English (US)",
isbn = "9783642222993",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "267--278",
booktitle = "Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings",
}