Computing shortest paths amid non-overlapping weighted disks
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914948748148736 |
|---|---|
| author | Bose, Prosenjit De Carufel, Jean-Lou Esteban, Guillermo Maheshwari, Anil |
| author_facet | Bose, Prosenjit De Carufel, Jean-Lou Esteban, Guillermo Maheshwari, Anil |
| contents | In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of $ n $ non-overlapping weighted disks in the plane. For a given parameter $ \varepsilon \in (0,1]$, the length of the approximate path is at most $ (1 +\varepsilon) $ times larger than the length of the actual shortest path. The algorithm is based on the discretization of the space by placing points on the boundary of the disks. Using such a discretization we can use Dijkstra's algorithm for computing a shortest path in the geometric graph obtained in (pseudo-)polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08869 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing shortest paths amid non-overlapping weighted disks Bose, Prosenjit De Carufel, Jean-Lou Esteban, Guillermo Maheshwari, Anil Computational Geometry In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of $ n $ non-overlapping weighted disks in the plane. For a given parameter $ \varepsilon \in (0,1]$, the length of the approximate path is at most $ (1 +\varepsilon) $ times larger than the length of the actual shortest path. The algorithm is based on the discretization of the space by placing points on the boundary of the disks. Using such a discretization we can use Dijkstra's algorithm for computing a shortest path in the geometric graph obtained in (pseudo-)polynomial time. |
| title | Computing shortest paths amid non-overlapping weighted disks |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2409.08869 |