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

Anne Driemel; Sariel Har-Peled; Carola Wenk

doi:10.1007/s00454-012-9402-z

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

Anne Driemel, Sariel Har-Peled, Carola Wenk

Siebel School of Computing and Data Science

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

Abstract

We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝ ^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 (US)
Pages (from-to)	94-127
Number of pages	34
Journal	Discrete and Computational Geometry
Volume	48
Issue number	1
DOIs	https://doi.org/10.1007/s00454-012-9402-z
State	Published - Jul 2012

Keywords

Approximation algorithms
Frechet distance
Realistic input models

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1007/s00454-012-9402-z

Library availability

Discover UIUC Full Text

Cite this

@article{9625c87bdd9b44d4bf7323fd1296b51f,

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

abstract = "We present a simple and practical (1+ε)-approximation algorithm for the Fr{\'e}chet distance between two polygonal curves in ℝ 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.",

keywords = "Approximation algorithms, Frechet distance, Realistic input models",

author = "Anne Driemel and Sariel Har-Peled and Carola Wenk",

note = "Funding Information: The work of A. Driemel has been supported by the Netherlands Organisation for Scientific Research (NWO) under RIMGA (Realistic Input Models for Geographic Applications). The work of S. Har-Peled was partially supported by a NSF AF award CCF-0915984. The work of C. Wenk has been supported by NSF CAREER award CCF-0643597. Funding Information: This research was initiated during a workshop supported by the Netherlands Organization for Scientific Research (NWO) under BRICKS/FOCUS grant number 642.065.503. ",

year = "2012",

month = jul,

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

language = "English (US)",

volume = "48",

pages = "94--127",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

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

AU - Driemel, Anne

AU - Har-Peled, Sariel

AU - Wenk, Carola

N1 - Funding Information: The work of A. Driemel has been supported by the Netherlands Organisation for Scientific Research (NWO) under RIMGA (Realistic Input Models for Geographic Applications). The work of S. Har-Peled was partially supported by a NSF AF award CCF-0915984. The work of C. Wenk has been supported by NSF CAREER award CCF-0643597. Funding Information: This research was initiated during a workshop supported by the Netherlands Organization for Scientific Research (NWO) under BRICKS/FOCUS grant number 642.065.503.

PY - 2012/7

Y1 - 2012/7

N2 - We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝ 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+ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝ 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.

KW - Approximation algorithms

KW - Frechet distance

KW - Realistic input models

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

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

U2 - 10.1007/s00454-012-9402-z

DO - 10.1007/s00454-012-9402-z

M3 - Article

AN - SCOPUS:84860888930

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

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this