@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",

}