Back to Search
Start Over
Computing the Fréchet distance between folded polygons.
- Source :
-
Computational Geometry . Dec2015, Vol. 50, p1-16. 16p. - Publication Year :
- 2015
-
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 ∞ in polynomial time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09257721
- Volume :
- 50
- Database :
- Academic Search Index
- Journal :
- Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 110100033
- Full Text :
- https://doi.org/10.1016/j.comgeo.2015.08.002