Fréchet distance for curves, revisited

Boris Aronov; Sariel Har-Peled; Christian Knauer; Yusu Wang; Carola Wenk

doi:10.1007/11841036_8

Fréchet distance for curves, revisited

Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the discrete Fréchet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves: κ-bounded curves and backbone curves, the latter of which are widely used to model molecular structures. We also propose a pseudo-output-sensitive algorithm for computing the discrete Fréchet distance exactly. The complexity of the algorithm is a function of the complexity of the free-space boundary, which is quadratic in the worst case, but tends to be lower in practice.

Original language	English (US)
Title of host publication	Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
Publisher	Springer
Pages	52-63
Number of pages	12
ISBN (Print)	3540388753, 9783540388753
DOIs	https://doi.org/10.1007/11841036_8
State	Published - 2006
Event	14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland Duration: Sep 11 2006 → Sep 13 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4168 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	14th Annual European Symposium on Algorithms, ESA 2006
Country/Territory	Switzerland
City	Zurich
Period	9/11/06 → 9/13/06

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/11841036_8

Library availability

Discover UIUC Full Text

Cite this

Aronov, B., Har-Peled, S., Knauer, C., Wang, Y., & Wenk, C. (2006). Fréchet distance for curves, revisited. In Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings (pp. 52-63). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS). Springer. https://doi.org/10.1007/11841036_8

Fréchet distance for curves, revisited. / Aronov, Boris; Har-Peled, Sariel; Knauer, Christian et al.
Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings. Springer, 2006. p. 52-63 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B, Har-Peled, S, Knauer, C, Wang, Y & Wenk, C 2006, Fréchet distance for curves, revisited. in Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4168 LNCS, Springer, pp. 52-63, 14th Annual European Symposium on Algorithms, ESA 2006, Zurich, Switzerland, 9/11/06. https://doi.org/10.1007/11841036_8

@inproceedings{3ba609f3e34645cb809afc9928d479ee,

title = "Fr{\'e}chet distance for curves, revisited",

abstract = "We revisit the problem of computing the Fr{\'e}chet distance between polygonal curves, focusing on the discrete Fr{\'e}chet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves: κ-bounded curves and backbone curves, the latter of which are widely used to model molecular structures. We also propose a pseudo-output-sensitive algorithm for computing the discrete Fr{\'e}chet distance exactly. The complexity of the algorithm is a function of the complexity of the free-space boundary, which is quadratic in the worst case, but tends to be lower in practice.",

author = "Boris Aronov and Sariel Har-Peled and Christian Knauer and Yusu Wang and Carola Wenk",

year = "2006",

doi = "10.1007/11841036_8",

language = "English (US)",

isbn = "3540388753",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "52--63",

booktitle = "Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings",

address = "Germany",

note = "14th Annual European Symposium on Algorithms, ESA 2006 ; Conference date: 11-09-2006 Through 13-09-2006",

}

TY - GEN

T1 - Fréchet distance for curves, revisited

AU - Aronov, Boris

AU - Har-Peled, Sariel

AU - Knauer, Christian

AU - Wang, Yusu

AU - Wenk, Carola

PY - 2006

Y1 - 2006

N2 - We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the discrete Fréchet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves: κ-bounded curves and backbone curves, the latter of which are widely used to model molecular structures. We also propose a pseudo-output-sensitive algorithm for computing the discrete Fréchet distance exactly. The complexity of the algorithm is a function of the complexity of the free-space boundary, which is quadratic in the worst case, but tends to be lower in practice.

AB - We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the discrete Fréchet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves: κ-bounded curves and backbone curves, the latter of which are widely used to model molecular structures. We also propose a pseudo-output-sensitive algorithm for computing the discrete Fréchet distance exactly. The complexity of the algorithm is a function of the complexity of the free-space boundary, which is quadratic in the worst case, but tends to be lower in practice.

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

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

U2 - 10.1007/11841036_8

DO - 10.1007/11841036_8

M3 - Conference contribution

AN - SCOPUS:33750699629

SN - 3540388753

SN - 9783540388753

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 52

EP - 63

BT - Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings

PB - Springer

T2 - 14th Annual European Symposium on Algorithms, ESA 2006

Y2 - 11 September 2006 through 13 September 2006

ER -

Fréchet distance for curves, revisited

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this