A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space

We propose a data structure for point sets 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₃, (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 O₃, (n n) time, using O₃, (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₃, (n) time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time O₃, (n). This is the first dynamic nearest neighbour data structure in hyperbolic space with proven efficiency guarantees.