Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909685669429248 |
|---|---|
| author | Spalding-Jamieson, Jack Naredla, Anurag Murty |
| author_facet | Spalding-Jamieson, Jack Naredla, Anurag Murty |
| contents | Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for the minimum-weight subset of the obstacles separating the two points. A few computational models for this problem have been previously studied. We give a unified approach to this problem in all models via a reduction to a particular shortest-path problem, and obtain improved running times in essentially all cases. In addition, we also give fine-grained lower bounds for many cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17289 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds Spalding-Jamieson, Jack Naredla, Anurag Murty Computational Geometry Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for the minimum-weight subset of the obstacles separating the two points. A few computational models for this problem have been previously studied. We give a unified approach to this problem in all models via a reduction to a particular shortest-path problem, and obtain improved running times in essentially all cases. In addition, we also give fine-grained lower bounds for many cases. |
| title | Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2504.17289 |