Computing the Fréchet distance between folded polygons

A.F. Cook IV, A. Driemel, J. Sherette, C. Wenk

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Abstract

Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known polynomial-time algorithm is limited to computing it between flat surfaces. We study the problem of computing the Fréchet distance for a class of non-flat surfaces called folded polygons. We present a fixed-parameter tractable algorithm for this problem. Next, we present a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fréchet distance for L_8 in polynomial time. Keywords: Fréchet distance; Surface comparison; Folded polygons
Original languageEnglish
Pages (from-to)1-16
JournalComputational Geometry
Volume50
Issue numberdec.
DOIs
Publication statusPublished - 2015

Fingerprint

Dive into the research topics of 'Computing the Fréchet distance between folded polygons'. Together they form a unique fingerprint.

Cite this