2026-07-22T08:26:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8786 2024-03-06T10:42:39Z ddc:004 open_access

New Bounds for Range Closest-Pair Problems Xue, Jie Li, Yuan Rahul, Saladi Janardan, Ravi Closest-pair Range search Candidate pairs Average-case analysis Given a dataset S of points in R^2, 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 cap 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jie Xue and Yuan Li and Saladi Rahul and Ravi Janardan 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.73 urn:nbn:de:0030-drops-87865 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.73 eng https://creativecommons.org/licenses/by/3.0/legalcode