Approximating the Fréchet distance when only one curve is $c$-packed
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929580089016320 |
|---|---|
| author | Gudmundsson, Joachim Mai, Tiancheng Wong, Sampson |
| author_facet | Gudmundsson, Joachim Mai, Tiancheng Wong, Sampson |
| contents | One approach to studying the Fréchet distance is to consider curves that satisfy realistic assumptions. By now, the most popular realistic assumption for curves is $c$-packedness. Existing algorithms for computing the Fréchet distance between $c$-packed curves require both curves to be $c$-packed. In this paper, we only require one of the two curves to be $c$-packed. Our result is a nearly-linear time algorithm that $(1+\varepsilon)$-approximates the Fréchet distance between a $c$-packed curve and a general curve in $\mathbb R^d$, for constant values of $\varepsilon$, $d$ and $c$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05114 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating the Fréchet distance when only one curve is $c$-packed Gudmundsson, Joachim Mai, Tiancheng Wong, Sampson Computational Geometry One approach to studying the Fréchet distance is to consider curves that satisfy realistic assumptions. By now, the most popular realistic assumption for curves is $c$-packedness. Existing algorithms for computing the Fréchet distance between $c$-packed curves require both curves to be $c$-packed. In this paper, we only require one of the two curves to be $c$-packed. Our result is a nearly-linear time algorithm that $(1+\varepsilon)$-approximates the Fréchet distance between a $c$-packed curve and a general curve in $\mathbb R^d$, for constant values of $\varepsilon$, $d$ and $c$. |
| title | Approximating the Fréchet distance when only one curve is $c$-packed |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2407.05114 |