Approximate range closest-pair queries

Jie Xue, Yuan Li, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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.

Original languageEnglish (US)
Article number101654
JournalComputational Geometry: Theory and Applications
Volume90
DOIs
StatePublished - Oct 2020

Bibliographical note

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

Publisher Copyright:
© 2020 Elsevier B.V.

Keywords

  • Approximate data structures
  • Closest pair
  • Range search

Fingerprint

Dive into the research topics of 'Approximate range closest-pair queries'. Together they form a unique fingerprint.

Cite this