Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.05708 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929306057310208 |
|---|---|
| author | Meinert, Nis |
| author_facet | Meinert, Nis |
| contents | Given two polygonal curves, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance which has many desirable properties but is notoriously expensive to calculate, especially for non-trivial metrics. In 1994, Eiter and Mannila introduced the discrete Fréchet distance which is much easier to implement and approximates the continuous Fréchet distance with a quadratic runtime overhead. However, this algorithm relies on recursions and is not well suited for modern hardware. To that end, we introduce the Fast Fréchet Distance algorithm, a recursion-free algorithm that calculates the discrete Fréchet distance with a linear memory overhead and that can utilize modern hardware more effectively. We showcase an implementation with only four lines of code and present benchmarks of our algorithm running fast on modern CPUs and GPGPUs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_05708 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Walking Your Frog Fast in 4 LoC Meinert, Nis Computational Geometry Given two polygonal curves, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance which has many desirable properties but is notoriously expensive to calculate, especially for non-trivial metrics. In 1994, Eiter and Mannila introduced the discrete Fréchet distance which is much easier to implement and approximates the continuous Fréchet distance with a quadratic runtime overhead. However, this algorithm relies on recursions and is not well suited for modern hardware. To that end, we introduce the Fast Fréchet Distance algorithm, a recursion-free algorithm that calculates the discrete Fréchet distance with a linear memory overhead and that can utilize modern hardware more effectively. We showcase an implementation with only four lines of code and present benchmarks of our algorithm running fast on modern CPUs and GPGPUs. |
| title | Walking Your Frog Fast in 4 LoC |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2404.05708 |