Closest-pair queries in fat rectangles

摘要

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 boolean AND 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(logn + 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. (C) 2019 Elsevier B.V. All rights reserved.