Score: 0
An $O(n\log n)$ Algorithm for Single-Source Shortest Paths in Disk Graphs
Published: June 9, 2025 |
arXiv ID: 2506.07571v1
By: Mark de Berg, Sergio Cabello
Potential Business Impact:
Finds fastest paths on special map shapes.
We prove that the single-source shortest-path problem on disk graphs can be solved in $O(n\log n)$ time, and that it can be solved on intersection graphs of fat triangles in $O(n\log^2 n)$ time.
Similar Papers
89%
An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
Computational Geometry
Finds shortest paths in circle maps faster.
8 Jul 2025
0
87%
Single-Source Shortest Path Problem in Weighted Disk Graphs
Data Structures and Algorithms
Finds fastest routes on maps with circles.
9 Apr 2025
1
86%
Shortcutting for Negative-Weight Shortest Path
Data Structures and Algorithms
Finds fastest routes in complex networks faster.
16 Nov 2025
2
Page Count
19 pages
Category
Computer Science:
Computational Geometry