A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa

Date

2024-06

Major/Subject

Mcode

Degree programme

Language

en

Pages

Series

Leibniz International Proceedings in Informatics, LIPIcs ; Volume 293

Abstract

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 create a Steiner spanner that achieves a spanning ratio of 1+ε with 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 an elegant solution to the approximate nearest neighbour problem: given a point set P in d-dimensional hyperbolic space we build the data structure in O_{d,ε}(nlog n) time, using O_{d,ε}(n) space. Then for any query point q we can find a point p ∈ P that is at most 1+ε times farther from q than its nearest neighbour in P in O_{d,ε}(log n) time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time O_{d,ε}(log n). This is the first dynamic nearest neighbour data structure in hyperbolic space with proven efficiency guarantees.

Description

Publisher Copyright: © Sándor Kisfaludi-Bak and Geert van Wordragen.

Keywords

dynamic approximate nearest neighbours, hyperbolic geometry, Steiner spanner

Other note

Citation

Kisfaludi-Bak, S & van Wordragen, G 2024, A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space . in W Mulzer & J M Phillips (eds), 40th International Symposium on Computational Geometry (SoCG 2024) ., 68, Leibniz International Proceedings in Informatics, LIPIcs, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Computational Geometry, Athens, Greece, 11/06/2024 . https://doi.org/10.4230/LIPIcs.SoCG.2024.68