Closest-Pair Queries in Fat Rectangles

Abstract

In the range closest pair problem, we want to construct a data structure storing a set $S$ of $n$ points in the plane, such that for any axes-parallel query rectangle $R$, the closest pair in the set $R\cap S$ can be reported. The currently best result for this problem is by Xue et al.~(SoCG 2018). Their data structure has size $O(n{\log }^{2}n)$ and query time $O({\log }^{2}n)$. We show that a data structure of size $O(n\log n)$ can be constructed in $O(n\log n)$ time, such that queries can be answered in $O(\log n+f\log f)$ time, where $f$ is the aspect ratio of $R$. Thus, for fat query rectangles, the query time is $O(\log n)$. This result is obtained by reducing the range closest pair problem to standard range searching problems on the points of $S$.

13 pages, revised version