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 -