New bounds for range closest-pair problems

Jie Xue, Yuan Li, Saladi Rahul, Ravi Janardan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Given a dataset S of points in R2, the range closest-pair (RCP) problem aims to preprocess S into a data structure such that when a query range X is specified, the closest-pair in S ∩ X can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.

Original languageEnglish (US)
Title of host publication34th International Symposium on Computational Geometry, SoCG 2018
EditorsCsaba D. Toth, Bettina Speckmann
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages731-7314
Number of pages6584
ISBN (Electronic)9783959770668
DOIs
StatePublished - Jun 1 2018
Event34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, Hungary
Duration: Jun 11 2018Jun 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume99
ISSN (Print)1868-8969

Other

Other34th International Symposium on Computational Geometry, SoCG 2018
CountryHungary
CityBudapest
Period6/11/186/14/18

Keywords

  • Average-case analysis
  • Candidate pairs
  • Closest-pair
  • Range search

Fingerprint Dive into the research topics of 'New bounds for range closest-pair problems'. Together they form a unique fingerprint.

  • Cite this

    Xue, J., Li, Y., Rahul, S., & Janardan, R. (2018). New bounds for range closest-pair problems. In C. D. Toth, & B. Speckmann (Eds.), 34th International Symposium on Computational Geometry, SoCG 2018 (pp. 731-7314). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 99). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2018.73