How Packed Is It, Really?
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915182412824576 |
|---|---|
| author | Har-Peled, Sariel Zhou, Timothy |
| author_facet | Har-Peled, Sariel Zhou, Timothy |
| contents | The congestion of a curve is a measure of how much it zigzags around locally. More precisely, a curve $π$ is $c$-packed if the length of the curve lying inside any ball is at most $c$ times the radius of the ball, and its congestion is the minimum $c$ for which $π$ is $c$-packed. This paper presents a randomized $42$-approximation algorithm for computing the congestion of a curve (or any set of segments in the plane). It runs in $O( n \log^2 n)$ time and succeeds with high probability. Although the approximation factor is large, the running time improves over the previous fastest constant approximation algorithm, which took $\widetilde{O}(n^{4/3})$ time. We carefully combine new ideas with known techniques to obtain our new near-linear time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_10776 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | How Packed Is It, Really? Har-Peled, Sariel Zhou, Timothy Computational Geometry The congestion of a curve is a measure of how much it zigzags around locally. More precisely, a curve $π$ is $c$-packed if the length of the curve lying inside any ball is at most $c$ times the radius of the ball, and its congestion is the minimum $c$ for which $π$ is $c$-packed. This paper presents a randomized $42$-approximation algorithm for computing the congestion of a curve (or any set of segments in the plane). It runs in $O( n \log^2 n)$ time and succeeds with high probability. Although the approximation factor is large, the running time improves over the previous fastest constant approximation algorithm, which took $\widetilde{O}(n^{4/3})$ time. We carefully combine new ideas with known techniques to obtain our new near-linear time algorithm. |
| title | How Packed Is It, Really? |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2105.10776 |