Computing the Fréchet Distance Between Folded Polygons

Date

2012-03-30

Authors

Cook, Atlas F. IV
Driemel, Anne
Sherette, Jessica
Wenk, Carola

Journal Title

Journal ISSN

Volume Title

Publisher

UTSA Department of Computer Science

Abstract

Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known 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 in polynomial time.

Description

Keywords

Citation

Department

Computer Science