On Small Pair Decompositions for Point Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910009538904064 |
|---|---|
| author | Buchin, Kevin Conradi, Jacobus Har-Peled, Sariel Kalb, Antonia Lahiri, Abhiruk Plätz, Lukas Rehs, Carolin Wong, Sampson |
| author_facet | Buchin, Kevin Conradi, Jacobus Har-Peled, Sariel Kalb, Antonia Lahiri, Abhiruk Plätz, Lukas Rehs, Carolin Wong, Sampson |
| contents | $\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algorithms in low-dimensional Euclidean space and doubling metrics. This problem is computationally hard already $\Re^2$, and is also hard to approximate.
We also introduce a new pair decomposition, removing the requirement that the diameters of the parts should be small. Surprisingly, we show that in a general metric space, one can compute such a decomposition of size $O( \tfrac{n}{\varepsilon}\log n)$, which is dramatically smaller than the quadratic bound for WSPDs. In $\Re^d$, the bound improves to $O( d \tfrac{n}{\varepsilon}\log \tfrac{1}{\varepsilon } )$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22728 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Small Pair Decompositions for Point Sets Buchin, Kevin Conradi, Jacobus Har-Peled, Sariel Kalb, Antonia Lahiri, Abhiruk Plätz, Lukas Rehs, Carolin Wong, Sampson Computational Geometry $\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algorithms in low-dimensional Euclidean space and doubling metrics. This problem is computationally hard already $\Re^2$, and is also hard to approximate. We also introduce a new pair decomposition, removing the requirement that the diameters of the parts should be small. Surprisingly, we show that in a general metric space, one can compute such a decomposition of size $O( \tfrac{n}{\varepsilon}\log n)$, which is dramatically smaller than the quadratic bound for WSPDs. In $\Re^d$, the bound improves to $O( d \tfrac{n}{\varepsilon}\log \tfrac{1}{\varepsilon } )$. |
| title | On Small Pair Decompositions for Point Sets |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2601.22728 |