Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	de Berg, Mark, Cabello, Sergio
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Single-Source Shortest Path Problem in Weighted Disk Graphs
by: An, Shinwoo, et al.
Published: (2025)

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
by: de Berg, Mark, et al.
Published: (2026)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2025)

Shortest Paths in Geodesic Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2026)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

Shortest Path Separators in Unit Disk Graphs
by: Harb, Elfarouk, et al.
Published: (2024)

The Contiguous Art Gallery Problem is in Θ(n log n)
by: de Berg, Sarita, et al.
Published: (2025)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Parametric Shortest Paths in a Linearly Interpolated Graph
by: Sriraman, Jacob, et al.
Published: (2026)

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
by: de Berg, Sarita, et al.
Published: (2023)

A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $\mathbb{R}^2$
by: Aronov, Boris, et al.
Published: (2024)

Shortest Paths of Mutually Visible Robots
by: Alsaedi, Rusul J., et al.
Published: (2023)

GASP: A Gradient-Aware Shortest Path Algorithm for Boundary-Confined Visualization of 2-Manifold Reeb Graphs
by: Rahman, Sefat E., et al.
Published: (2025)

On Stable Approximation Algorithms for Geometric Coverage Problems
by: de Berg, Mark, et al.
Published: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

Counting of Shortest Paths in Cubic Grid
by: Dutt, Mousumi, et al.
Published: (2018)

Shortest Paths on Convex Polyhedral Surfaces
by: Wang, Haitao
Published: (2025)

Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs
by: Klost, Katharina, et al.
Published: (2024)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

Algorithms for Distance Problems in Continuous Graphs
by: Cabello, Sergio, et al.
Published: (2025)

Searching in Euclidean Spaces with Predictions
by: Cabello, Sergio, et al.
Published: (2024)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited
by: Zhao, Lihao, et al.
Published: (2025)

A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon
by: de Berg, Mark, et al.
Published: (2024)

Eliminating Crossings in Ordered Graphs
by: Agrawal, Akanksha, et al.
Published: (2024)

Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing
by: Ahrens, Markus, et al.
Published: (2021)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Improved Bounds for Discrete Voronoi Games
by: de Berg, Mark, et al.
Published: (2026)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
by: Manna, Bubai
Published: (2025)

On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons
by: de Berg, Mark, et al.
Published: (2026)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2025)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
by: Gao, Jie, et al.
Published: (2025)

Finding a Shortest Curve that Separates Few Objects from Many
by: Biedl, Therese, et al.
Published: (2025)

Dynamic Connectivity in Disk Graphs
by: Baumann, Alexander, et al.
Published: (2021)

Clustering with Few Disks to Minimize the Sum of Radii
by: Abrahamsen, Mikkel, et al.
Published: (2023)

Subcoloring of (Unit) Disk Graphs
by: Marin, Malory, et al.
Published: (2025)

An Algorithm for Illuminating $n$ Nonoverlapping Circular Discs' Boundaries on the Plane with Application to Tree Stem Illumination Problem
by: Sukkasem, Phapaengmuang, et al.
Published: (2025)

Landscapes of the Tetrahedron and Cube: An Exploration of Shortest Paths on Polyhedra
by: Fontenot, Kenzie, et al.
Published: (2022)