TY - JOUR
T1 - Computing the Fréchet distance between simple polygons
AU - Buchin, K.
AU - Buchin, M.
AU - Wenk, C.
PY - 2008
Y1 - 2008
N2 - We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fréchet distance, and develop an algorithm for computing the Fréchet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming.
AB - We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fréchet distance, and develop an algorithm for computing the Fréchet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming.
U2 - 10.1016/j.comgeo.2007.08.003
DO - 10.1016/j.comgeo.2007.08.003
M3 - Article
SN - 0925-7721
VL - 41
SP - 2
EP - 20
JO - Computational Geometry
JF - Computational Geometry
IS - 1-2
ER -