TY - JOUR

T1 - Approximate range closest-pair queries

AU - Xue, Jie

AU - Li, Yuan

AU - Janardan, Ravi

PY - 2020/10

Y1 - 2020/10

N2 - 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.

AB - 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.

KW - Approximate data structures

KW - Closest pair

KW - Range search

UR - http://www.scopus.com/inward/record.url?scp=85084221095&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084221095&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2020.101654

DO - 10.1016/j.comgeo.2020.101654

M3 - Article

AN - SCOPUS:85084221095

VL - 90

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

M1 - 101654

ER -