TY - GEN

T1 - The fréchet distance revisited and extended

AU - Har-Peled, Sariel

AU - Raichel, Benjamin

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - Given two simplicial complexes in IRd, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Fré chetdistance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of weak Fré chet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm we can solve a slew of new problems, from computing a mean curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the mean curve problem, when the k input curves are c-packed, one can (1 + ")-approximate the mean curve in near linear time, for fixed k and ". Additionally, we present an algorithm for computing the strong Fré chet distance between two curves, which is simpler than previous algorithms, and avoids using parametric search.

AB - Given two simplicial complexes in IRd, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Fré chetdistance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of weak Fré chet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm we can solve a slew of new problems, from computing a mean curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the mean curve problem, when the k input curves are c-packed, one can (1 + ")-approximate the mean curve in near linear time, for fixed k and ". Additionally, we present an algorithm for computing the strong Fré chet distance between two curves, which is simpler than previous algorithms, and avoids using parametric search.

KW - Approximation algorithms

KW - Fréchet distance

KW - Realistic input Models

UR - http://www.scopus.com/inward/record.url?scp=79960165296&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960165296&partnerID=8YFLogxK

U2 - 10.1145/1998196.1998269

DO - 10.1145/1998196.1998269

M3 - Conference contribution

AN - SCOPUS:79960165296

SN - 9781450306829

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 448

EP - 457

BT - Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11

T2 - 27th Annual ACM Symposium on Computational Geometry, SCG'11

Y2 - 13 June 2011 through 15 June 2011

ER -