Two Optimization Problems for Unit Disks

2017/02/10 by Sergio Cabello, Cabello, Sergio, Lazar Milinković +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1702.03266

openalex publication_date 2017/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an implementation of a recent algorithm to compute shortest-path trees in unit disk graphs in O(nlog n) worst-case time, where n is the number of disks. In the minimum-separation problem, we are given n unit disks and two points s and t, not contained in any of the disks, and we want to compute the minimum number of disks one needs to retain so that any curve connecting s to t intersects some of the retained disks. We present a new algorithm solving this problem in O(n²log³ n) worst-case time and its implementation.

Cited by

• Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane

Related

• Shortest Paths in Intersection Graphs of Unit Disks
• An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
• An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
• Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
• Reverse Shortest Path Problem for Unit-Disk Graphs