2026-07-23T04:50:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24239 2025-11-12T13:39:17Z ddc:004 open_access

Tight Bounds on the Number of Closest Pairs in Vertical Slabs Biniaz, Ahmad Bose, Prosenjit Chung, Chaeyoon De Carufel, Jean-Lou Iacono, John Maheshwari, Anil Odak, Saeed Smid, Michiel Tóth, Csaba D. closest pair vertical slab data structure Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmad Biniaz and Prosenjit Bose and Chaeyoon Chung and Jean-Lou De Carufel and John Iacono and Anil Maheshwari and Saeed Odak and Michiel Smid and Csaba D. Tóth 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.8 urn:nbn:de:0030-drops-242391 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode