Computing the Frchet distance between folded polygons ?
Computing the Frchet 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 Frchet 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 Frchet distance for L? L ? in polynomial time.
frchet distance folded polygons surface comparison