The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916725735292928 |
|---|---|
| author | van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina |
| author_facet | van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina |
| contents | The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in $\mathbb{R}^d$: near-quadratic time algorithms exist, and conditional lower bounds suggest that these results cannot be improved significantly, even in one dimension and when approximating with a factor less than three. We consider the special case where the curves bound a simple polygon and distances are measured via geodesics inside this simple polygon. Here the conditional lower bounds do not apply; Efrat $et$ $al.$ (2002) were able to give a near-linear time $2$-approximation algorithm.
In this paper, we significantly improve upon their result: we present a $(1+\varepsilon)$-approximation algorithm, for any $\varepsilon > 0$, that runs in $\mathcal{O}(\frac{1}{\varepsilon} (n+m \log n) \log nm \log \frac{1}{\varepsilon})$ time for a simple polygon bounded by two curves with $n$ and $m$ vertices, respectively. To do so, we show how to compute the reachability of specific groups of points in the free space at once, by interpreting the free space as one between separated one-dimensional curves. We solve this one-dimensional problem in near-linear time, generalizing a result by Bringmann and Künnemann (2015). Finally, we give a linear time exact algorithm if the two curves bound a convex polygon. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03834 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina Computational Geometry F.2.2 The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in $\mathbb{R}^d$: near-quadratic time algorithms exist, and conditional lower bounds suggest that these results cannot be improved significantly, even in one dimension and when approximating with a factor less than three. We consider the special case where the curves bound a simple polygon and distances are measured via geodesics inside this simple polygon. Here the conditional lower bounds do not apply; Efrat $et$ $al.$ (2002) were able to give a near-linear time $2$-approximation algorithm. In this paper, we significantly improve upon their result: we present a $(1+\varepsilon)$-approximation algorithm, for any $\varepsilon > 0$, that runs in $\mathcal{O}(\frac{1}{\varepsilon} (n+m \log n) \log nm \log \frac{1}{\varepsilon})$ time for a simple polygon bounded by two curves with $n$ and $m$ vertices, respectively. To do so, we show how to compute the reachability of specific groups of points in the free space at once, by interpreting the free space as one between separated one-dimensional curves. We solve this one-dimensional problem in near-linear time, generalizing a result by Bringmann and Künnemann (2015). Finally, we give a linear time exact algorithm if the two curves bound a convex polygon. |
| title | The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon |
| topic | Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2501.03834 |