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 language | English |
---|---|
Pages (from-to) | 1-16 |
Journal | Computational Geometry |
Volume | 50 |
Issue number | dec. |
DOIs | |
Publication status | Published - 2015 |