Searching for the closest-pair in a query translate

Jie Xue, Yuan Li, Saladi Rahul, Ravi Janardan

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

1 Scopus citations

Abstract

We consider a range-search variant of the closest-pair problem. Let Γ be a fixed shape in the plane. We are interested in storing a given set of n points in the plane in some data structure such that for any specified translate of Γ, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Γ is a polygon (possibly with holes) and when Γ is a general convex body whose boundary is smooth. When Γ is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Γ is a general convex body with a smooth boundary, we give a near-optimal data structure using O(nlog n) space and O(log2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018.

Original languageEnglish (US)
Title of host publication35th International Symposium on Computational Geometry, SoCG 2019
EditorsGill Barequet, Yusu Wang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771047
DOIs
StatePublished - Jun 1 2019
Event35th International Symposium on Computational Geometry, SoCG 2019 - Portland, United States
Duration: Jun 18 2019Jun 21 2019

Publication series

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

Conference

Conference35th International Symposium on Computational Geometry, SoCG 2019
CountryUnited States
CityPortland
Period6/18/196/21/19

    Fingerprint

Keywords

  • And phrases Closest pair
  • Geometric data structures
  • Range search
  • Translation query

Cite this

Xue, J., Li, Y., Rahul, S., & Janardan, R. (2019). Searching for the closest-pair in a query translate. In G. Barequet, & Y. Wang (Eds.), 35th International Symposium on Computational Geometry, SoCG 2019 [61] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 129). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2019.61