An O(nlog n) Algorithm for Single-Source Shortest Paths in Disk Graphs

2025/06/09 by de Berg, Mark, Cabello, Sergio · 2 citations
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2506.07571

Abstract

We prove that the single-source shortest-path problem on disk graphs can be solved in O(nlog n) time, and that it can be solved on intersection graphs of fat triangles in O(nlog² n) time.

Citations

• Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• Shortest Paths in Intersection Graphs of Unit Disks

Cited by

• Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
• An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Related

• Single-Source Shortest Path Problem in Weighted Disk Graphs
• Shortest Paths in Intersection Graphs of Unit Disks
• An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
• Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
• Improved Distributed Algorithms for Exact Shortest Paths