Approximating the Fréchet distance for realistic curves in near linear time

A. Driemel; S. Har-Peled; C. Wenk

doi:10.1007/s00454-012-9402-z

Approximating the Fréchet distance for realistic curves in near linear time

A. Driemel
, S. Har-Peled
, C. Wenk

Research output: Contribution to journal › Article › Academic › peer-review

105 Citations (Scopus)

129 Downloads (Pure)

Abstract

We present a simple and practical (1+e)-approximation algorithm for the Fréchet distance between two polygonal curves in R^d. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.

Original language	English
Pages (from-to)	94-127
Journal	Discrete and Computational Geometry
Volume	48
Issue number	1
DOIs	https://doi.org/10.1007/s00454-012-9402-z
Publication status	Published - 2012
Externally published	Yes

Access to Document

10.1007/s00454-012-9402-z

publishers versionFinal published version, 1.07 MB

Cite this

@article{8a5aa31509bb418091503313eb8916ec,

title = "Approximating the Fr{\'e}chet distance for realistic curves in near linear time",

abstract = "We present a simple and practical (1+e)-approximation algorithm for the Fr{\'e}chet distance between two polygonal curves in R\textasciicircum{}d. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.",

author = "A. Driemel and S. Har-Peled and C. Wenk",

year = "2012",

doi = "10.1007/s00454-012-9402-z",

language = "English",

volume = "48",

pages = "94--127",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Approximating the Fréchet distance for realistic curves in near linear time

AU - Driemel, A.

AU - Har-Peled, S.

AU - Wenk, C.

PY - 2012

Y1 - 2012

N2 - We present a simple and practical (1+e)-approximation algorithm for the Fréchet distance between two polygonal curves in R^d. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.

AB - We present a simple and practical (1+e)-approximation algorithm for the Fréchet distance between two polygonal curves in R^d. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.

U2 - 10.1007/s00454-012-9402-z

DO - 10.1007/s00454-012-9402-z

M3 - Article

SN - 0179-5376

VL - 48

SP - 94

EP - 127

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Approximating the Fréchet distance for realistic curves in near linear time

Abstract

Access to Document

Fingerprint

Cite this