The range closest-pair (RCP) problem, as a range-search version of the classical closest-pair problem, aims to store a dataset of points in some data structure such that whenever a query range Q is given, the closest-pair inside Q can be reported efficiently. In this paper, we study the approximate version of the RCP problem with two approximation criteria. The first criterion is in terms of the query range, which allows the returned answer to be slight outside the specified query range. The second criterion is in terms of the quality of the answer, which allows the returned pair to be slightly more distant than the true answer. We establish some interesting connections between the approximate RCP problem (with the above two criteria) and classical range-search problems, namely, range reporting and range minimum, by giving general reductions between them.
Bibliographical noteFunding Information:
A preliminary version appeared at the 30th Canadian Conference on Computational Geometry, 2018. The research of Jie Xue is supported, in part, by a Doctoral Dissertation Fellowship from The Graduate School of the University of Minnesota.
© 2020 Elsevier B.V.
- Approximate data structures
- Closest pair
- Range search