Computing the Fréchet Distance Between Folded Polygons

Details Computing the Fréchet Distance Between Folded Polygons Computing the Fréchet Distance Between Folded Polygons

2011-03-15

arxiv.org/abs/1103.2865v1

Computer Science

Computational Geometry

19 pages, 10 figures. Submitted to WADS 2011

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing the Fréchet Distance Between Folded Polygons does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the Fréchet Distance Between Folded Polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Fréchet Distance Between Folded Polygons will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-138610