What question did this study set out to answer?

To develop an efficient algorithm for solving the single-source shortest-path problem in disk graphs and fat triangle intersection graphs.

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.

Bookmark

View Full Paper