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

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 log<sup>3</sup> n) time.

Authors

Institutions

Publication Details

Journal
TU/e Research Portal
Published
2025-10-01
DOI
https://doi.org/10.4230/lipics.esa.2025.81
Primary Topic
Computational Geometry and Mesh Generation
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

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

Sergio Cabello, Mark; id_orcid 0000-0001-5770-3784 de Berg
TU/e Research Portal
Computational Geometry and Mesh Generation
article

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

Sergio Cabello, Mark; id_orcid 0000-0001-5770-3784 de Berg
article en

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 log<sup>3</sup> n) time.

TU/e Research Portal
University of Ljubljana (SI), ACT Foundation (US), Computer Algorithms for Medicine (AT), Institute of Mathematics, Physics, and Mechanics (SI)
Openalex Percentile: Top 13%
Computational Geometry and Mesh Generation
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.