Deterministic algorithms match randomized speed for point distance selection
Deterministic Distance Selection in $O(n^{4/3})$ Time
Computational GeometryData Structures and Algorithms
Summary
The problem is to find the K-th smallest distance between points in a set, which has many applications but is computationally challenging. Previous solutions either used randomness or took longer to run deterministically. The paper presents a new deterministic algorithm that runs as fast as the best randomized one for this task in the plane. It also improves the method for a related problem involving distances between two different point sets. These advances make it possible to reliably find specific distances more efficiently without relying on chance.
What this means in practice
- •For geospatial analytics teams: Compute precise rankings of distances among geographic points quickly without relying on randomness, improving reliability in spatial data analysis.
- •For robotics navigation engineers: Determine exact distance thresholds between robot positions and obstacles faster to enhance path planning algorithms.
Authors
Haitao Wang
Abstract
Let $P$ be a set of $n$ points in the plane. Given an integer $K$ with $1\le K\le {n\choose 2}$, the distance selection problem asks for the $K$-th smallest distance among all pairwise distances of the points of $P$. The problem has been studied extensively over the past four decades. Recently, Chan and Zheng (2023) gave a randomized algorithm with $O(n^{4/3})$ expected running time, while the best known deterministic algorithm runs in $O(n^{4/3}\log n)$ time. In this paper, we present a deterministic $O(n^{4/3})$-time algorithm for the problem, matching the best known randomized complexity. We also consider the more general bichromatic version of the problem, where two point sets $A$ and $B$ are given, with $m=|A|$ and $n=|B|$, and the goal is to find the $K$-th smallest distance among the $mn$ distances between points of $A$ and points of $B$. For this problem, the best previously known algorithm runs in $O((m\log n+n\log m+m^{2/3}n^{2/3})\log(m+n))$ time. We present a new deterministic algorithm with running time $O(m\log^2 n+n\log^2 m+m^{2/3}n^{2/3})$.