Approximate range closest-pair queries [journal]

Journal

Computational Geometry - April 24, 2020

Authors

Jie Xue (Ph.D. 2019), Yuan Li (Ph.D. 2017), Ravi Janardan (professor)

Abstract

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.

Link to full paper

Approximate range closest-pair queries

Keywords

geometric computing