TY - GEN
T1 - Approximating the Fréchet distance for realistic curves in near linear time
AU - Driemel, Anne
AU - Har-Peled, Sariel
AU - Wenk, Carola
PY - 2010
Y1 - 2010
N2 - We present a simple and practical (1+ε)-approximation algorithm for the Fréchet 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, and show similar results for other input models, such as low density.
AB - We present a simple and practical (1+ε)-approximation algorithm for the Fréchet 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, and show similar results for other input models, such as low density.
KW - Approximation algorithms
KW - Fréchet distance
KW - Realistic input models
UR - http://www.scopus.com/inward/record.url?scp=77954939479&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954939479&partnerID=8YFLogxK
U2 - 10.1145/1810959.1811019
DO - 10.1145/1810959.1811019
M3 - Conference contribution
AN - SCOPUS:77954939479
SN - 9781450300162
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 365
EP - 374
BT - Proceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
T2 - 26th Annual Symposium on Computational Geometry, SoCG 2010
Y2 - 13 June 2010 through 16 June 2010
ER -