Efficient Algorithms for the Bottleneck Path Problem in Geometric Graphs

2026/08/04 by Matthew J. Katz, Rachel Saban, Micha Sharir
Computer Science · #cs.CG

paper · pdf

arxiv created 2026/08/04 · arxiv updated 2026/08/06

Abstract

We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna angles bounded from below by a constant, and visibility graphs whose vertices lie on or above a 1.5-dimensional terrain, both with Euclidean distances as edge weights. We provide near-linear algorithms for the corresponding decision problems, namely, determining whether the subgraph obtained by retaining all edges with weight at most some threshold \bf bn contains a path from s to t. We then use the decision procedures to obtain algorithms for the bottleneck path problem that run in O^*(n^8/7) randomized expected time, where n is the input size and the O^*(⋅) notation hides subpolynomial factors. Within the same performance bounds, we can also solve the bounded-hop version, in which we only consider s-t paths with at most k edges, for a given integer k < n.

Citations

• An O(nlog n) Algorithm for Single-Source Shortest Paths in Disk Graphs
• Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
• The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs
• Reverse Shortest Path Problem for Unit-Disk Graphs
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints
• Shortest Paths in Intersection Graphs of Unit Disks
• The Discrete and Semi-continuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques
• Maintenance of configurations in the plane