TY - JOUR
T1 - The Fréchet distance revisited and extended
AU - Har-Peled, Sariel
AU - Raichel, Benjamin
N1 - Funding Information:
Work on this article was partially supported by an NSF AF award CCF-0915984. The authors thank Anne Driemel, Jeff Erickson, Steve LaValle, Jessica Sherette, and Carola Wenk for useful discussions on the problems studied in this article. The authors would also like to thank the reviewers for their insightful comments.
Publisher Copyright:
© 2014 ACM.
PY - 2014/1
Y1 - 2014/1
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 weak Fréchet distance 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 weak Fréchet distance 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 - Algorithms
KW - Approximation algorithms
KW - F.2.2 [analysis of algorithms and problem complexity]: nonnumerical algorithms and problems - geometrical problems and computations
KW - Fréchet distance
KW - Realistic input models
KW - Theory
UR - http://www.scopus.com/inward/record.url?scp=84995677049&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84995677049&partnerID=8YFLogxK
U2 - 10.1145/2532646
DO - 10.1145/2532646
M3 - Article
AN - SCOPUS:84995677049
SN - 1549-6325
VL - 10
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 1
M1 - 3
ER -