An O(n log n) Algorithm for Single-Source Shortest Paths in Disk Graphs | Synapse
March 29, 2026Open Access
An O(n log n) Algorithm for Single-Source Shortest Paths in Disk Graphs
Key Points
To develop an efficient algorithm for solving the single-source shortest-path problem in disk graphs and fat triangle intersection graphs.
Proposed an algorithm with O(n log n) expected time complexity for disk graphs.
Extended the algorithm to intersection graphs of fat triangles with O(n log^3 n) time complexity.
Demonstrated the efficiency of the algorithm for disk graphs with O(n log n) performance.
Showed that fat triangle intersection graphs can be managed with a higher but still efficient time complexity of O(n log^3 n).
Abstract
We prove that the single-source shortest-path problem on disk graphs can be solved in O(n log n) expected time, and that it can be solved on intersection graphs of fat triangles in O(n log3 n) time.