A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909761295876096 |
|---|---|
| author | Kisfaludi-Bak, Sándor van Wordragen, Geert |
| author_facet | Kisfaludi-Bak, Sándor van Wordragen, Geert |
| contents | We propose a data structure in $d$-dimensional hyperbolic space that can be considered a natural counterpart to quadtrees in Euclidean spaces. Based on this data structure we propose a so-called L-order for hyperbolic point sets, which is an extension of the Z-order defined in Euclidean spaces.
Using these quadtrees and the L-order we build geometric spanners. Near-linear size $(1+ε)$-spanners do not exist in hyperbolic spaces, but we are able to create a Steiner spanner that achieves a spanning ratio of $1+ε$ with $\mathcal O_{d,ε}(n)$ edges, using a simple construction that can be maintained dynamically. As a corollary we also get a $(2+ε)$-spanner (in the classical sense) of the same size, where the spanning ratio $2+ε$ is almost optimal among spanners of subquadratic size.
Finally, we show that our Steiner spanner directly provides a solution to the approximate nearest neighbour problem: given a point set $P$ in $d$-dimensional hyperbolic space we build the data structure in $\mathcal O_{d,ε}(n\log n)$ time, using $\mathcal O_{d,ε}(n)$ space. Then for any query point $q$ we can find a point $p\in P$ that is at most $1+ε$ times farther from $q$ than its nearest neighbour in $P$ in $\mathcal O_{d,ε}(\log n)$ time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time $\mathcal O_{d,ε}(\log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_01356 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space Kisfaludi-Bak, Sándor van Wordragen, Geert Computational Geometry We propose a data structure in $d$-dimensional hyperbolic space that can be considered a natural counterpart to quadtrees in Euclidean spaces. Based on this data structure we propose a so-called L-order for hyperbolic point sets, which is an extension of the Z-order defined in Euclidean spaces. Using these quadtrees and the L-order we build geometric spanners. Near-linear size $(1+ε)$-spanners do not exist in hyperbolic spaces, but we are able to create a Steiner spanner that achieves a spanning ratio of $1+ε$ with $\mathcal O_{d,ε}(n)$ edges, using a simple construction that can be maintained dynamically. As a corollary we also get a $(2+ε)$-spanner (in the classical sense) of the same size, where the spanning ratio $2+ε$ is almost optimal among spanners of subquadratic size. Finally, we show that our Steiner spanner directly provides a solution to the approximate nearest neighbour problem: given a point set $P$ in $d$-dimensional hyperbolic space we build the data structure in $\mathcal O_{d,ε}(n\log n)$ time, using $\mathcal O_{d,ε}(n)$ space. Then for any query point $q$ we can find a point $p\in P$ that is at most $1+ε$ times farther from $q$ than its nearest neighbour in $P$ in $\mathcal O_{d,ε}(\log n)$ time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time $\mathcal O_{d,ε}(\log n)$. |
| title | A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2305.01356 |