Approximating the Frechet Distance for Realistic Curves in Near Linear Time

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

Approximating the Frechet Distance for Realistic Curves in Near Linear Time

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

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We present a simple and practical (1+\eps)-approximation algorithm for the Frechet distance between polygonal curves. 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 in Rd, and show similar results for other input models, such as low density.

Original language	English
Title of host publication	Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010
Editors	J. Snoeyink, M. de Berg, J.S.B. Mitchell, G. Rote, M. Teillaud
Publisher	Association for Computing Machinery
Pages	365-374
Number of pages	10
Publication status	Published - 13 Jun 2010

Bibliographical note

26th ACM Symposium on Computational Geometry

Cite this

@inproceedings{b37d844617614fc6a3fdd53e841c4e30,

title = "Approximating the Frechet Distance for Realistic Curves in Near Linear Time",

abstract = "We present a simple and practical (1+\textbackslash{}eps)-approximation algorithm for the Frechet distance between polygonal curves. 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 in Rd, and show similar results for other input models, such as low density.",

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

note = "26th ACM Symposium on Computational Geometry",

year = "2010",

month = jun,

day = "13",

language = "English",

pages = "365--374",

editor = "J. Snoeyink and \{de Berg\}, M. and J.S.B. Mitchell and G. Rote and M. Teillaud",

booktitle = "Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010",

publisher = "Association for Computing Machinery",

address = "United States",

}

Approximating the Frechet Distance for Realistic Curves in Near Linear Time. / Driemel, A.; Har-Peled, S.; Wenk, C.
Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010. ed. / J. Snoeyink; M. de Berg; J.S.B. Mitchell; G. Rote; M. Teillaud. Association for Computing Machinery, 2010. p. 365-374.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximating the Frechet Distance for Realistic Curves in Near Linear Time

AU - Driemel, A.

AU - Har-Peled, S.

AU - Wenk, C.

N1 - 26th ACM Symposium on Computational Geometry

PY - 2010/6/13

Y1 - 2010/6/13

N2 - We present a simple and practical (1+\eps)-approximation algorithm for the Frechet distance between polygonal curves. 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 in Rd, and show similar results for other input models, such as low density.

AB - We present a simple and practical (1+\eps)-approximation algorithm for the Frechet distance between polygonal curves. 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 in Rd, and show similar results for other input models, such as low density.

M3 - Conference contribution

SP - 365

EP - 374

BT - Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010

A2 - Snoeyink, J.

A2 - de Berg, M.

A2 - Mitchell, J.S.B.

A2 - Rote, G.

A2 - Teillaud, M.

PB - Association for Computing Machinery

ER -

Approximating the Frechet Distance for Realistic Curves in Near Linear Time

Abstract

Bibliographical note

Fingerprint

Cite this