Tight Bounds on the Number of Closest Pairs in Vertical Slabs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910898782732288 |
|---|---|
| author | Biniaz, Ahmad Bose, Prosenjit Chung, Chaeyoon De Carufel, Jean-Lou Iacono, John Maheshwari, Anil Odak, Saeed Smid, Michiel Tóth, Csaba D. |
| author_facet | Biniaz, Ahmad Bose, Prosenjit Chung, Chaeyoon De Carufel, Jean-Lou Iacono, John Maheshwari, Anil Odak, Saeed Smid, Michiel Tóth, Csaba D. |
| contents | Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \geq 2$ is a constant, and let $H_1,H_2,\ldots,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 \leq i < j \leq 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 \leq m \leq 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 \cap 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_17600 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 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. Computational Geometry Data Structures and Algorithms Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \geq 2$ is a constant, and let $H_1,H_2,\ldots,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 \leq i < j \leq 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 \leq m \leq 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 \cap 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. |
| title | Tight Bounds on the Number of Closest Pairs in Vertical Slabs |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.17600 |