Approximate range closest-pair search

Jie Xue, Yuan Li, Ravi Janardan

Research output: Contribution to conferencePaperpeer-review

5 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. This paper studies an approximate version of the RCP problem in which the answer pair is allowed to be “approximately” contained in the query range. A general reduction from the approximate RCP problem to the range-minimum and range-reporting problems is given, which works for a general class of query spaces. The reduction is applied to obtain efficient approximate RCP data structures for disk queries in ℝ2 and ball queries in higher dimensions. Finally, the paper also shows that for orthogonal queries, the approximate RCP problem is (asymptotically) at least as hard as the orthogonal range-minimum problem.

Original languageEnglish (US)
Pages282-287
Number of pages6
StatePublished - Jan 1 2018
Event30th Canadian Conference on Computational Geometry, CCCG 2018 - Winnipeg, Canada
Duration: Aug 8 2018Aug 10 2018

Conference

Conference30th Canadian Conference on Computational Geometry, CCCG 2018
CountryCanada
CityWinnipeg
Period8/8/188/10/18

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

Cite this