2026-08-18T07:43:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10465 2024-03-06T10:46:03Z ddc:004 open_access

Searching for the Closest-Pair in a Query Translate Xue, Jie Li, Yuan Rahul, Saladi Janardan, Ravi Closest pair Range search Geometric data structures Translation query We consider a range-search variant of the closest-pair problem. Let Gamma 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 Gamma, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Gamma is a polygon (possibly with holes) and when Gamma is a general convex body whose boundary is smooth. When Gamma is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Gamma is a general convex body with a smooth boundary, we give a near-optimal data structure using O(n log n) space and O(log^2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jie Xue and Yuan Li and Saladi Rahul and Ravi Janardan 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.61 urn:nbn:de:0030-drops-104659 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.61 eng https://creativecommons.org/licenses/by/3.0/legalcode