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 | |
| Publication status | Published - 2012 |
| Externally published | Yes |
Fingerprint Dive into the research topics of 'Approximating the Fréchet distance for realistic curves in near linear time'. Together they form a unique fingerprint.
Cite this
Driemel, A., Har-Peled, S., & Wenk, C. (2012). Approximating the Fréchet distance for realistic curves in near linear time. Discrete and Computational Geometry, 48(1), 94-127. https://doi.org/10.1007/s00454-012-9402-z