Single-Source Shortest Path Problem in Weighted Disk Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909572140105728 |
|---|---|
| author | An, Shinwoo Oh, Eunjin Xue, Jie |
| author_facet | An, Shinwoo Oh, Eunjin Xue, Jie |
| contents | In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in the plane. Here, the weight of an edge is defined as the Euclidean distance between the centers of the disks corresponding to the endpoints of the edge. Given a family of $n$ disks in the plane whose radii lie in $[1,Ψ]$ and a source disk, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^2 n \log Ψ)$ time. Moreover, in the case that the radii of disks are arbitrarily large, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^4 n)$ time. This improves the best-known algorithm running in $O(n\log^6 n)$ time presented in ESA'23. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06534 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Single-Source Shortest Path Problem in Weighted Disk Graphs An, Shinwoo Oh, Eunjin Xue, Jie Data Structures and Algorithms Computational Geometry In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in the plane. Here, the weight of an edge is defined as the Euclidean distance between the centers of the disks corresponding to the endpoints of the edge. Given a family of $n$ disks in the plane whose radii lie in $[1,Ψ]$ and a source disk, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^2 n \log Ψ)$ time. Moreover, in the case that the radii of disks are arbitrarily large, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^4 n)$ time. This improves the best-known algorithm running in $O(n\log^6 n)$ time presented in ESA'23. |
| title | Single-Source Shortest Path Problem in Weighted Disk Graphs |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2504.06534 |