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∩S can be reported. The currently best result for this problem is by Xue et al. (SoCG 2018). Their data structure has size O(nlog 2 ⁡n) and query time O(log 2 ⁡n). We show that a data structure of size O(nlog⁡n) can be constructed in O(nlog⁡n) time, such that queries can be answered in O(log⁡n+flog⁡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.

, , , ,
Computational Geometry
Computational Geometry Lab

Bae, S.W. (Sang Won), & Smid, M. (2019). Closest-pair queries in fat rectangles. Computational Geometry. doi:10.1016/j.comgeo.2019.05.003