arsinh artanh dist % Department of Computer Science, Aalto University,
<EMAIL_ADDRESS>Department of Computer Science, Aalto
University<EMAIL_ADDRESS>Sándor Kisfaludi-Bak and Geert
van Wordragen [500]Theory of computation Data structures design and analysis
[500]Theory of computation Computational geometry John Q. Open and Joan R.
Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT
2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# A Quadtree for Hyperbolic Space000This is an abstract of a presentation
given at CG:YRF 2023. It has been made public for the benefit of the community
and should be considered a preprint rather than a formally reviewed paper.
Thus, this work is expected to appear in a conference with formal proceedings
and/or in a journal.

Sándor Kisfaludi-Bak  Geert van Wordragen

###### 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. We
demonstrate the usefulness of our hyperbolic quadtree data structure by giving
an algorithm for constant-approximate closest pair and dynamic constant-
approximate nearest neighbours in hyperbolic space of constant dimension $d$.

###### keywords:

Hyperbolic geometry, quadtree, approximate nearest neighbour

##  1 Introduction

Hyperbolic geometry has applications in several fields, including special
relativity, topology, visualisation, machine learning, complex network
modelling, etc. [19, 17, 15, 16, 14]. With the growing interest in the larger
scientific community, there are growing computational and
graphical/visualisation needs. It is becoming increasingly important to
develop basic data structures and algorithms for hyperbolic spaces.

Quadtrees in Euclidean spaces [9] are among the few geometric data structures
that have proven to be useful both in practical algorithms and in theory [1,
8, 10]. They form the basis of various data structures by being able to ‘zoom
in’ efficiently. Quadtrees provide a hierarchical structure, as well as a way
to think of ordering points of the plane (or higher-dimensional spaces) using
the so-called Z-order curve. They can be used as a basis for nearest neighbour
algorithms [10]. The central question addressed by this article is as follows.

> Is there a natural hyperbolic equivalent to Euclidean quadtrees?

Given a point set $P$ in the Euclidean plane (henceforth denoted by
$\mathbb{R}^{2}$), a quadtree of $P$ can be defined as follows. Let
$\sigma_{0}$ be a minimal axis-parallel square containing $P$, and let $T$ be
a tree graph whose root corresponds to $\sigma_{0}$. Then consider a square
$\sigma$ and the corresponding vertex $v_{\sigma}$ of $T$ where $|\sigma\cap
P|\geq 2$ (starting with $\sigma=\sigma_{0}$). We subdivide $\sigma$ into four
squares of half the side length of $\sigma$. Each smaller square is associated
with a new vertex that is connected to $v_{\sigma}$. This procedure is
repeated for each square $\sigma$ where $\sigma\cap P\geq 2$ exhaustively,
until all leaves of $T$ correspond to squares that contain at most one point
from $P$. The squares are called the _cells_ of the quadtree, and we can speak
of parent/child and ancestor/descendant relationships of cells by applying the
terms of the corresponding vertices in $T$. The _level_ of a cell or vertex is
its distance to the root of $T$ along the shortest path in $T$ (i.e., the root
has level $0$).

Some crucial properties of Euclidean quadtrees are used by several algorithms.

  1. 1.

If $C^{\prime}$ is a child cell of $C$, then
$c_{1}<\mathrm{diam}(C^{\prime})/\mathrm{diam}(C)<c_{2}$ where
$0<c_{1}<c_{2}<1$ are fixed constants, and $\mathrm{diam}(C)$ denotes the
diameter of the cell $C$.

  2. 2.

Each cell $C$ contains a ball that has diameter at least constant times the
diameter of $C$. Thus cells are so-called _fat_ objects in $\mathbb{R}^{2}$.

  3. 3.

Each cell has at most $k$ children cells for some fixed constant $k$.

  4. 4.

Cells of the same level are isometric, that is, any cell can be obtained from
any other cell of the same level by using a distance-preserving
transformation.

Could the above four properties be replicated by a quadtree in the hyperbolic
plane? Unfortunately this is not possible: the volume of a ball in hyperbolic
space grows exponentially with its radius (thus hyperbolic spaces are not
_doubling spaces_). Consequently, for large cells, a cell of constant times
smaller diameter than its parent will only cover a vanishingly small volume of
its parent. This rules out having properties 1, 2, and 3 together. Property 4
also poses a unique challenge: while the hyperbolic plane provides many types
of  _tilings_ one could start with, there is no transformation that would be
equivalent to scaling in Euclidean spaces. This is unlike the scaling-
invariance exhibited by Euclidean quadtrees. Moreover, in small neighbourhoods
hyperbolic spaces are locally Euclidean, meaning that a small ball in
hyperbolic space can be embedded into a Euclidean ball of the same radius with
distortion infinitesimally close to 1. Thus a hyperbolic quadtree needs to
operate at two different scales: at small distances we need to work with an
almost-Euclidean metric, while at larger distances we need to work on a non-
doubling metric.

#### Our contribution

We propose a hyperbolic quadtree that satisfies properties 1, 2, as well as
property 4 in case of cells of super-constant diameter. Moreover, our
hyperbolic quadtree resembles a Euclidean quadtree for cells of sub-constant
diameter. Based on the quadtree we are able to construct a new order and
space-filling curve, named the L-order, which serves as a hyperbolic extension
of the Euclidean Z-order. We show that a few hyperbolic quadtrees (and
corresponding L-orders) can create a useful cover of $\mathbb{H}^{d}$ in the
following sense.

######  Theorem 1.1.

For any $\Delta\in\mathbb{R}_{+}$, there is a set of at most $3d+3$ infinite
hyperbolic quadtrees such that any two points $p,q\in\mathbb{H}^{d}$ with
$\dist_{\mathbb{H}^{d}}(p,q)\leq\Delta$ are contained in a cell with diameter
$\mathcal{O}{\left(d\sqrt{d}\right)}\cdot\dist_{\mathbb{H}^{d}}(p,q)$ in one
of the quadtrees.

The above theorem matches the Euclidean result given by Chan, Har-Peled and
Jones [6, Lemma 3.7]. We demonstrate the usefulness of our new data structure
by presenting two applications related to approximate nearest neighbours. A
pair $p,p^{\prime}\in P$ of distinct points is a _$c$ -approximate closest
pair_ in $P$ if $\dist(p,p^{\prime})\leq c\cdot\min_{{a,a^{\prime}\in P,\
a\neq a^{\prime}}}\dist(a,a^{\prime})$. Given the point set $P$ and some query
point $q$ in the ambient space, we say that $p\in P$ is a _$c$ -approximate
nearest neighbour_ of $q$ if $\dist(q,p)\leq c\cdot\min_{a\in P}\dist(q,a)$.

######  Theorem 1.2.

Let $P\subset\mathbb{H}^{d}$ be a given set of $n$ points.

  * •

We can find an $\mathcal{O}{\left(d\sqrt{d}\right)}$-approximate closest pair
of $P$ in $\mathcal{O}{\left(d^{2}n\log n\right)}$ time.

  * •

We can construct a data structure in $\mathcal{O}{\left(d^{2}n\log n\right)}$
time that uses $\mathcal{O}{\left(d^{2}n\right)}$ space and can answer queries
for an $\mathcal{O}{\left(d\sqrt{d}\right)}$-approximate nearest neighbour in
$P$ in $\mathcal{O}{\left(d^{2}\log n\right)}$ time, and perform updates
(point insertions and removals) in $\mathcal{O}{\left(d^{2}\log n\right)}$
time.

A natural next step is to extend the above to $(1+\varepsilon)$-approximate
nearest neighbours as in [6]. Unfortunately this fails to give $o(n)$ query
times when $\mathrm{diam}(P)=\log n$, so the problem is left for future work.

#### Related work

Approximate nearest neighbour search in hyperbolic spaces has been studied by
Krauthgamer and Lee [13] and by Wu and Charikar [20]. Krauthgamer and Lee
describe a data structure of size $\mathcal{O}{\left(n^{2}\right)}$ that
allows queries for a $\mathcal{O}{\left(1\right)}$-additive approximation of
the nearest neighbour in $\mathcal{O}{\left(\log^{2}n\right)}$ time. They note
that this can be further improved to a $(1+\varepsilon)$-approximation using
[12]. Wu and Charikar describe various practical methods of using black-box
algorithms for Euclidean nearest neighbour search to find exact and
$(1+\varepsilon)$-approximate nearest neighbours.

##  2 Preliminaries

We assume that the reader is familiar with the basics of hyperbolic geometry
and trigonometry, as well as the Poincaré half-space model. For more
background on hyperbolic geometry, please see [4] and the textbooks [11, 18,
2]. Note that our results are presented in the half-space model, but are in
fact model-independent. Our algorithms are also presented for point sets whose
coordinates are given in the half-space model. Apart from numerical challenges
—something we will not tackle in this article—, working in the half-space
model is not restrictive as conversion between various models of hyperbolic
geometry is straightforward.

Let $\mathbb{H}^{d}$ denote the $d$-dimensional hyperbolic space of sectional
curvature $-1$. We denote points as $(x,z)$ for $x\in\mathbb{R}^{d-1}$ and
$z\in\mathbb{R}^{+}$, with the distance

$\dist_{\mathbb{H}^{d}}((x,z),(x^{\prime},z^{\prime}))=2\arsinh\left(\frac{1}{2}\sqrt{\frac{\|x-x^{\prime}\|^{2}+(z-z^{\prime})^{2}}{zz^{\prime}}}\right),$

where $\|x\|$ refers to the $(d-1)$-dimensional Euclidean norm of $x$. When
$x=x^{\prime}$ this reduces to
$\left|\ln\left(\frac{z}{z^{\prime}}\right)\right|$.

For the rest of the paper, we fix a particular half-space model, and describe
our results in this model. Note that there are standard ways to convert
between different models, allowing the results to be used also for inputs
defined in different models. We will think of the $z$ direction as going “up”,
and the $d-1$ other axes are going “sideways”.

The transformations $T_{\sigma,\tau}(x,z)=(\sigma x+\tau,\sigma z)$, where we
scale all coordinates by $\sigma\in\mathbb{R}^{+}$ and then translate $x$ with
a vector $\tau\in\mathbb{R}^{d-1}$, are isometric. This can be verified by
applying $T_{\sigma,\tau}$ to both arguments in the distance formula. In fact,
any isometry of $(d-1)$-dimensional Euclidean space induces a hyperbolic
isometry.

Consider now the translations $T_{\sigma,\tau}$ where $\sigma=2^{k}$ for some
integer $k$ and $\tau$ is an integer vector. One can observe that acting upon
the Euclidean unit cube with corners $(0,\dots,0,1)$ and $(1,\dots,1,2)$ these
translations create a tiling of the half-space model with isometric tiles.
This tiling has been named the _binary tiling_ , and it was introduced by
Böröczky[3]. The binary tiling is the basis of our quadtree construction. The
$2$-dimensional binary tiling is illustrated in Figure 1.

Figure 1: A portion of the binary tiling in the half-plane model

Fix a point $p$ and a hyperplane $h$ in $\mathbb{H}^{d}$. (Here hyperplane is
understood in the hyperbolic sense, i.e. in the half-space model it is either
a $d-1$-dimensional hemisphere perpendicular to $z=0$ or a hyperplane
perpendicular to $z=0$.) The _reflection_ of $p$ on $h$ is a point
$p^{\prime}$ such that the geodesic $pp^{\prime}$ is perpendicular to $h$, and
the midpoint $t$ of $pp^{\prime}$ is on $h$. We call $t$ the _hyperbolic
projection_ of $p$ onto $h$.

######  Lemma 2.1.

The distance from $(x,z)\in\mathbb{H}^{d}$ to the hyperplane $x_{1}=0$ is
$\arsinh\frac{|x_{1}|}{z}$.

######  Proof 2.2.

Mirroring $(x,z)$ in the hyperplane gives a point $(x^{\prime},z)$ where
$x^{\prime}_{1}=-x_{1}$ but still $x^{\prime}_{i}=x_{i}$ for all other $i$.
Let $p$ be the projection of $(x,z)$ onto the $z$-axis. This point must be
exactly in the middle of the line segment connecting $(x,z)$ and its mirror
image:
$\dist_{\mathbb{H}^{d}}((x,z),p)=\frac{1}{2}\dist_{\mathbb{H}^{d}}((x,z),(x^{\prime},z))=\arsinh{\frac{|x_{1}|}{z}}$.

We will use $\log$ to denote the base-$2$ logarithm.

##  3 A hyperbolic quadtree

The Euclidean quadtree is a tree whose vertices are associated with axis-
parallel hypercubes. Correspondingly, our hyperbolic quadtree will be a tree
whose vertices are associated with so-called _cube-based horoboxes_. For this
paper, it will be useful to define an _axis-parallel horobox_ as the shape
that corresponds to a Euclidean axis-parallel box in a fixed half-space model.
Notice that a horobox is bounded by 2 horospheres and $2(d-1)$ hyperplanes.
The cube-based horobox is a special axis-parallel horobox, defined as follows.

######  Definition 3.1.

In a fixed half-space model, a _cube-based horobox_ $R(x,z,w,h)$ is a
Euclidean box with corner points $(x,z)$ and $(x+z\cdot(w,\dots,w),z\cdot
2^{h})$. We call $w$ its _width_ and $h$ its _height_.

It is worth noting that at $z=1$, the width corresponds to the Euclidean width
of the horobox. On top of that, defining the width and height in this way
ensures that horoboxes with the same width and height are congruent to one
another: $T_{\sigma,\tau}$ transforms a horobox $R(x,z,w,h)$ into
$R(x^{\prime},z^{\prime},w,h)$ when
$\sigma=\frac{z^{\prime}}{z},\tau=x^{\prime}-x\cdot\frac{z^{\prime}}{z}$.

######  Lemma 3.2.

Horobox $C=R(x,z,w,h)$ has diameter
$\mathrm{diam}(C)=2\arsinh\left(\frac{1}{2}w\sqrt{d-1}\right)$ when
$w\geq\sqrt{\frac{2^{h}-1}{d-1}}$ and
$\mathrm{diam}(C)=2\arsinh\left(\frac{1}{2}\sqrt{\frac{(d-1)w^{2}+(2^{h}-1)^{2}}{2^{h}}}\right)$
otherwise.

######  Proof 3.3.

The distance $\dist_{\mathbb{H}^{d}}((x,z),(x^{\prime},z^{\prime}))$ is
monotone increasing in $\|x-x^{\prime}\|$. Assuming $z^{\prime}\leq z$, the
distance is also monotone decreasing in $z^{\prime}$. This means the diameter
is w.l.o.g. given by
$\dist_{\mathbb{H}^{d}}\left((0,z),((w,\dots,w),1)\right)=2\arsinh\left(\frac{1}{2}\sqrt{\frac{(d-1)w^{2}+(z-1)^{2}}{z}}\right)$,
for some $1\leq z\leq 2^{h}$.

In this interval the function is convex in $z$, so the maximum is attained at
either $z=1$ or $z=2^{h}$. Thus it is either
$2\arsinh\left(\frac{1}{2}w\sqrt{d-1}\right)$ or
$2\arsinh\left(\frac{1}{2}\sqrt{\frac{(d-1)w^{2}+(2^{h}-1)^{2}}{2^{h}}}\right)$.
These are equal when $w=\sqrt{\frac{2^{h}-1}{d-1}}$. Both are continuous, so
it suffices to check two combinations of values to see that $z=1$ gives the
largest value if and only if $w\geq\sqrt{\frac{2^{h}-1}{d-1}}$.

###  3.1 Hyperbolic quadtree construction.

One property of hyperbolic space that makes quadtrees more complicated is that
it behaves differently at different scales: in small enough neighbourhoods the
distortion compared to Euclidean space approaches one, but at larger scales
the hyperbolic nature becomes more and more pronounced. This means that the
quadtree also has to work differently at different scales.

For a point set $P\subset\mathbb{H}^{d}$, the hyperbolic quadtree
$\mathcal{Q}(P)$ is a graph whose vertices are regions of hyperbolic space. We
can construct $\mathcal{Q}(P)$ as follows. First, we find the Euclidean
minimum bounding box of $P$ in the half-space model. From this we can get a
minimum bounding horobox $R(x,z,w,h)$ where $z=\min_{p\in P}\pi_{z}(p)$ (i.e.,
we shift the horobox up as much as possible).

In case of $d=2$, our goal is to ensure that quadtree cells of level $\ell\geq
0$ correspond to horoboxes whose vertices come from a fixed binary tiling. The
levels can be constructed starting at level $\ell=0$, where cells are the
tiles of a binary tiling. The binary tiling is closely related to binary
trees: we get a binary tree from the tiling by making a graph where each
vertex corresponds to a horobox and edges correspond to them being vertically
adjacent. When we have a binary tree, we can partition it into a small number
of identical subgraphs by ‘cutting’ at half its depth, see Figure 2. This
gives a natural way to split cells of level $\ell\geq 1$ into $1+2^{\ell}$
isomorphic cells, one corresponding to the ’top’ part of the binary tree, and
the rest corresponding to the subtrees defined by the vertices at depth
$\ell$. When splitting cells of level $\ell\leq 0$, we are already in a
setting where the distortion is very small compared to the Euclidean setting;
here we simply use Euclidean dissection into four smaller cells, each with the
same Euclidean width and hyperbolic height.

Figure 2: Left: A quadtree cell of level $2$ is split into $5$ cells of level
$1$. Right: The binary tree of depth $4$ is split into $5$ isomorphic binary
trees of depth $2$.

For general $d$, we define the quadtree as follows:

  * •

If111Notice that the $1/\sqrt{d-1}$ terms in this definition simplify the
diameter formula of quadtree cells, making them independent of $d$: see Lemma
3.4. $w\leq\frac{1}{\sqrt{d-1}}$ and $h\leq 1$, we find the smallest integer
$\ell$ such that $w\leq\frac{2^{\ell}}{\sqrt{d-1}}$ and $h\leq 2^{\ell}$, then
use $R(x,z,\frac{2^{\ell}}{\sqrt{d-1}},2^{\ell})$ as the root cell of our
quadtree.

  * •

Otherwise, we find the smallest integer $\ell$ such that
$w\leq\frac{2^{2^{\ell}-1}}{\sqrt{d-1}}$ and $h\leq 2^{\ell}$, then use
$R(x,z,\frac{2^{2^{\ell}-1}}{\sqrt{d-1}},2^{\ell})$ as the root cell.

We then subdivide cells to get their children, but unlike with the Euclidean
quadtree this subdivision depends on the size of the cell. If we have a cell
$R(x^{\prime},z^{\prime},w,h)$ with $h\leq 1$, then we split it into $2^{d}$
smaller ones using the Euclidean hyperplanes
$x_{i}=x_{i}^{\prime}+\frac{w}{2z}$ and $z=z^{\prime}\cdot 2^{\frac{h}{2}}$.
For larger $h$, we also use the Euclidean hyperplane $z=z^{\prime}\cdot
2^{\frac{h}{2}}$. This gives two horoboxes with height $h/2$, where the top
one has width $w/2^{\frac{h}{2}}$ but the bottom one still $w$. Thus, we also
split the bottom horobox into a grid of $2^{\frac{h}{2}(d-1)}$ horoboxes of
width $w/2^{\frac{h}{2}}$ so that in total we have $2^{\frac{h}{2}(d-1)}+1$
cells of the same size.

Figure 3: A hyperbolic quadtree where the root (red) is a level $2$ cell,
which is split into five isometric cells of level $1$ that are separated by
blue Euclidean segments.

######  Lemma 3.4.

At any level $\ell$, cells are cube-based horoboxes with height $2^{\ell}$.
For $\ell\geq 0$, the width is $\frac{2^{2^{\ell}-1}}{\sqrt{d-1}}$ and the
diameter is $2\arsinh(2^{2^{\ell}-2})$. For $\ell<0$, the width is
$\frac{\alpha\cdot 2^{\ell}}{\sqrt{d-1}}$ and the diameter is
$2\arsinh\left(\frac{1}{2}\sqrt{\frac{\alpha^{2}\cdot
4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}\right)$, where
$\alpha\in\left(\frac{1}{2},1\right]$ is a cell-specific value. Moreover, if a
cell $C$ of level $\ell$ has corresponding value $\alpha$ and a child cell
$C^{\prime}$ of $C$ has corresponding value $\alpha^{\prime}$, then
$\alpha^{\prime}/\alpha\in\\{1,2^{-2^{\ell-1}}\\}$.

######  Proof 3.5.

The statement for $\ell\geq 0$ follows directly from the construction and
Lemma 3.2. At $\ell\leq 0$, a cell of width $w$ and height $h$ gets split into
four cells that all have height $h/2$, where the lower two have width
$\frac{w}{2}$ and the upper two have width $\frac{w}{2}/2^{\frac{h}{2}}$. At
level 0 the height is $1$ and the width $\frac{1}{\sqrt{d-1}}$, so cells at
level $\ell<0$ have height $2^{\ell}$ and width $\frac{\alpha\cdot
2^{\ell}}{\sqrt{d-1}}$, for a yet to be determined value $\alpha$. Its lower
two child cells have width $\frac{w}{2}=\frac{\alpha\cdot
2^{\ell-1}}{\sqrt{d-1}}$, while the upper two have width
$\frac{w}{2}/2^{\frac{h}{2}}=\frac{\alpha\cdot
2^{\ell-1}}{2^{2^{\ell-1}}\sqrt{d-1}}$. Thus the width of the child cells
follows the same formula, with $\alpha$ the same or replaced by $\alpha\cdot
2^{-2^{\ell-1}}$. At $\ell=0$ we have $\alpha=1$, thus it is also the highest
value it can take for other cells. The lowest possible value of $\alpha$ at
level $\ell$ is given by
$\prod_{i=\ell+1}^{0}2^{-2^{i-1}}=2^{-\sum_{i=\ell}^{-1}2^{i}}=2^{2^{\ell}-1}>\frac{1}{2}$.

######  Theorem 3.6.

The hyperbolic quadtree of $P\subset\mathbb{H}^{d}$ has the following
properties:

  1. 1.

If $C^{\prime}$ is a child cell of $C$, then
$0.42<\mathrm{diam}(C^{\prime})/\mathrm{diam}(C)<0.561$.

  2. 2.

Cells are $\Omega(1/\sqrt{d})$-fat.

  3. 3.

A quadtree cell $C$ has at most
$\max(2^{d},2^{\mathcal{O}{\left(d\cdot\mathrm{diam}(C)\right)}})$ children;
in particular, the root has
$\max(2^{d},d^{\mathcal{O}{\left(d\cdot\mathrm{diam}(P)\right)}})$ children.

  4. 4.

Cells of the same level $\ell\geq 0$ are isometric, and cells of level
$\ell<0$ are cube-based horoboxes with the same height whose width differs by
less than a factor two.

######  Proof 3.7.

  1. 1.

First assume $C$ is a cell at level $\ell\geq 4$ with child $C^{\prime}$. Then
by Lemma 3.4,
$\frac{\mathrm{diam}(C^{\prime})}{\mathrm{diam}(C)}=\frac{2\arsinh\left(2^{2^{\ell-1}-2}\right)}{2\arsinh\left(2^{2^{\ell}-2}\right)}$.
Here we can use $\ln 2x<\arsinh x<\ln 4x$ to get  (22ℓ-1-2)(22ℓ-2) ¡ ln(4
⋅22ℓ-1-2)ln(2 ⋅22ℓ-2) = 2ℓ-12ℓ\- 1 = 12 \+ 12ℓ\+ 1\- 2 ≤815
(22ℓ-1-2)(22ℓ-2) ¿ ln(2 ⋅22ℓ-1-2)ln(4 ⋅22ℓ-2) = 2ℓ-1\- 12ℓ = 12 \- 2^-ℓ ≥716

Now assume $C$ is at level $\ell\leq-2$. Then by Lemma 3.4,

$\frac{\mathrm{diam}(C^{\prime})}{\mathrm{diam}(C)}=\frac{2\arsinh\left(\frac{1}{2}\sqrt{\frac{(\alpha^{\prime})^{2}\cdot
4^{\ell-1}+(2^{2^{\ell-1}}-1)^{2}}{2^{2^{\ell-1}}}}\right)}{2\arsinh\left(\frac{1}{2}\sqrt{\frac{\alpha^{2}\cdot
4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}\right)},$

where $\alpha$ corresponds to $C$ and $\alpha^{\prime}$ to $C^{\prime}$. From
the proof of Lemma 3.4 it follows that either $\alpha^{\prime}=\alpha$ or
$\alpha^{\prime}=\alpha\cdot 2^{-2^{\ell-1}}$. First, we look for an upper
bound. We observe that in the denominator, the argument $x$ of $\arsinh x$ is
between $0$ and $0.15$, thus we may assume $\arsinh x>0.997x$. For the
positive numerator we can use that $\arsinh x\leq x$. This gives

$\frac{2\arsinh\left(\frac{1}{2}\sqrt{\frac{(\alpha^{\prime})^{2}\cdot
4^{\ell-1}+(2^{2^{\ell-1}}-1)^{2}}{2^{2^{\ell-1}}}}\right)}{2\arsinh\left(\frac{1}{2}\sqrt{\frac{\alpha^{2}\cdot
4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}\right)}<\frac{2^{2^{\ell-2}}}{0.997}\sqrt{\frac{(\alpha^{\prime})^{2}\cdot
4^{\ell-1}+(2^{2^{\ell-1}}-1)^{2}}{\alpha^{2}\cdot
4^{\ell}+(2^{2^{\ell}}-1)^{2}}}.$

We can also use that $\alpha^{\prime}\leq\alpha$, that
$(2^{2^{\ell}}-1)^{2}\geq 0$ and that $(2^{2^{\ell-1}}-1)^{2}<0.07\cdot
4^{\ell}$ for $\ell\leq-2$, giving

$\frac{2^{2^{\ell-2}}}{0.997}\sqrt{\frac{(\alpha^{\prime})^{2}\cdot
4^{\ell-1}+(2^{2^{\ell-1}}-1)^{2}}{\alpha^{2}\cdot
4^{\ell}+(2^{2^{\ell}}-1)^{2}}}<\frac{2^{2^{\ell-2}}}{0.997}\sqrt{\frac{1.07\cdot
4^{\ell-1}}{4^{\ell}}}<0.55.$

To prove a lower bound we work similarly. We now additionally use that
$\alpha^{\prime}\geq 2^{-2^{\ell-1}}\alpha$ and that
$(2^{2^{\ell}}-1)^{2}<0.15\cdot 4^{\ell}$ for $\ell\leq-2$, giving
2(12(α’)2⋅4ℓ-1\+ (22ℓ-1-1)222ℓ-1)2(12α2⋅4ℓ\+ (22ℓ-1)222ℓ) &¿ 0.997 ⋅2^2^ℓ-2
(α’)2⋅4ℓ-1\+ (22ℓ-1-1)2α2⋅4ℓ\+ (22ℓ-1)2
≥0.997 4ℓ-14ℓ\+ (22ℓ-1)2
¿ 0.997 4ℓ-11.15 ⋅4ℓ
¿ 0.46.

This proves the statement for $\ell\leq-2$ and $\ell\geq 4$. We check the
remaining cases in Table 1. The lower bound comes from $\ell=2$ and the upper
bound from $\ell=0$ with $\alpha^{\prime}=1$.

$\ell$ | -1 | 0 | 1 | 2 | 3
---|---|---|---|---|---
$\alpha$ | $1/\sqrt{2}$ | $1$ | 1 |  |  |
$\alpha^{\prime}$ | $1/\sqrt[4]{8}$ | $1/\sqrt{2}$ | $1/\sqrt[4]{2}$ | $1$ | $1/\sqrt{2}$ | $1$ |  |  |
| 0.485 | 0.5218 | 0.4795 | 0.5312 | 0.4718 | 0.5605 | 0.526 | 0.4208 | 0.4317
Table 1: Ratios between the diameter of a child cell and the diameter of its
level $\ell$ parent, up to four decimal places.

  2. 2. Figure 4: The two possible situations for the inscribed ball of a cube-based horobox, with last coordinates indicated as well as the Euclidean width of the rectangle in the second case.

For a cell $C=R(x,z,w,h)$, the inscribed ball will touch the bounding
horospheres at the top and bottom, or the bounding hyperplanes at the sides;
see Figure 4. The hyperbolic diameter of a ball is given by the distance
between its highest and lowest point. In the first case this is
$\ln\left(\frac{z\cdot 2^{h}}{z}\right)=h\ln 2$. In the second case, we only
know the ball’s Euclidean diameter is $z\cdot w$, but from that we can
calculate that the highest point of the ball is at height $z+z\cdot w$, so the
distance is $\ln\left(\frac{z+z\cdot w}{z}\right)=\ln(w+1)$.

In general the diameter of the inscribed ball is the smallest of these two. We
will show that for quadtree cells this is always
$\Omega\left(\ln(w+1)\right)$. At level $\ell$, the first case gives $h\ln
2=\ln\left(2^{2^{\ell}}\right)$ for every cell. In the second case, for
$\ell\geq 0$ we have
$\ln(w+1)=\ln\left(\frac{2^{2^{\ell}-1}}{\sqrt{d-1}}+1\right)$, which is at
most $\ln\left(2^{2^{\ell}}+1-\frac{1}{2}\cdot 2^{2^{\ell}}\right)$ and thus
smaller. For $\ell<0$ we have $\ln(w+1)\leq\ln\left(\frac{1\cdot
2^{\ell}}{\sqrt{d-1}}+1\right)$ by Lemma 3.4, which is at most
$\frac{2^{\ell}}{\sqrt{d-1}}$ and thus $h\ln 2=\Omega\left(\ln(w+1)\right)$.

Next we show that the diameter of $C$ is always
$\mathcal{O}{\left(2^{\ell}\right)}$. For $\ell\geq 0$,

$\mathrm{diam}(C)=2\arsinh(2^{2^{\ell}-2})=\mathcal{O}{\left(2^{\ell}\right)}$

and also for $\ell<0$,

$\mathrm{diam}(C)=2\arsinh\left(\frac{1}{2}\sqrt{\frac{\alpha^{2}\cdot
4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}\right)=\mathcal{O}{\left(\sqrt{\frac{4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}\right)}=\mathcal{O}{\left(2^{\ell}\right)}.$

We need to divide the diameter of the inscribed ball by the diameter of the
circumscribed ball to get the fatness. Notice that $2\mathrm{diam}(C)$ is an
upper bound on the diameter of the circumscribed ball. First assume $w<1$ and
$\ell<0$. Then the fatness is at least

$\frac{\Omega\left(\ln(w+1)\right)}{\mathcal{O}{\left(2^{\ell}\right)}}=\Omega\left(\frac{w}{2^{\ell}}\right)=\Omega\left(\frac{2^{\ell}}{2^{\ell}\sqrt{d}}\right)=\Omega\left(\frac{1}{\sqrt{d}}\right).$

Now assume $\ell\geq 0$ instead.

$\frac{\Omega\left(\ln(w+1)\right)}{\mathcal{O}{\left(2^{\ell}\right)}}=\Omega\left(\frac{w}{2^{\ell}}\right)=\Omega\left(\frac{2^{2^{\ell}}}{2^{\ell}\sqrt{d}}\right)=\Omega\left(\frac{1}{\sqrt{d}}\right).$

Finally, assume $w\geq 1$, which means automatically means $\ell\geq 0$ and
$2^{2^{\ell}-1}\geq\sqrt{d-1}$.

$\frac{\Omega\left(\ln(w+1)\right)}{\mathcal{O}{\left(2^{\ell}\right)}}=\Omega\left(\frac{\log
w}{2^{\ell}}\right)=\Omega\left(\frac{2^{\ell}+\log\frac{1}{d}}{2^{\ell}}\right)=\Omega\left(1\right).$

  3. 3.

Consider a quadtree cell $C$ of level $\ell$. If $\ell\leq 0$ then it has
$2^{d}$ children, so we now consider $\ell>0$. There we have
$\mathrm{diam}(C)=2\arsinh(2^{2^{\ell}-2})$ by Lemma 3.4, which means
$2^{2^{\ell}}=4\sinh(\frac{1}{2}\mathrm{diam}(C))$. The number of children of
$C$ is

$2^{\frac{2^{\ell}}{2}(d-1)}+1=\left(4\sinh\left(\frac{1}{2}\mathrm{diam}(C)\right)\right)^{\frac{1}{2}(d-1)}+1=2^{\mathcal{O}{\left(d\cdot\mathrm{diam}(C)\right)}}.$

Now we will prove the result for the root of the quadtree. Assume this root
lies at level $\ell>0$, because otherwise it has $2^{d}$ children. By
construction, we know that no quadtree cell $C$ of level $\ell-1$ can cover
$P$. In particular this means that the inscribed ball $B$ of $C$ cannot cover
$P$, meaning $\mathrm{diam}(P)>\mathrm{diam}(B)$. In (2) we showed
$\mathrm{diam}(B)=\ln\left(\frac{2^{2^{\ell-1}-1}}{\sqrt{d-1}}+1\right)$, so
$2^{2^{\ell-1}}=2\sqrt{d-1}(e^{\mathrm{diam}(B)}-1)$. This means the number of
children under the root is

$2^{\frac{2^{\ell}}{2}(d-1)}+1=\left(2\sqrt{d-1}\left(e^{\mathrm{diam}(B)}-1\right)\right)^{d-1}+1=d^{\mathcal{O}{\left(d\cdot\mathrm{diam}(P)\right)}}.$

  4. 4.

This follows from Lemma 3.4.

###  3.2 Covering with hyperbolic quadtrees

Euclidean quadtrees are useful in computing nearest neighbours and other
related problems because of a particular distance property: there is a small
collection of quadtrees one can define such that any pair of points at
distance $\delta$ will be contained in a cell of diameter
$\mathcal{O}{\left(\delta\right)}$ in one of the quadtrees. Moreover, the
quadtrees can be generated by simply taking one quadtree and translating
(_shifting_) it with different vectors.

We will prove an analogous property for our hyperbolic quadtrees, though our
“shifts” are the transformations $T_{\sigma,\tau}$ instead of translations.
Let us first introduce an infinite quadtree.

Consider the binary tiling that contains the Euclidean hypercube with opposite
corners $(0,\dots,0,1)$ and $(1,\dots,1,2)$. This tiling forms level $0$ of
the infinite quadtree $\mathcal{Q}^{d}_{\infty}$. Then each level $\ell<0$ is
defined by subdividing these cells according to the construction in Section
3.1. For $\ell>0$ we define the level $\ell$ cells by unifying
$2^{(d-1)\ell}+1$ cells of level $\ell-1$ into a horobox, doing the splitting
described in Section 3.1 in reverse. We do the unification in such a way that
the Euclidean hyperplanes $x_{i}=0$ for $i=1,\dots,d-1$ as well as $z=0$
remain cell boundaries at each level $\ell$. More formally, cells of level
$\ell$ are the horoboxes

$R\left(a\cdot\frac{2^{2^{\ell}-1}}{\sqrt{d-1}},2^{b\cdot
2^{\ell}},\frac{2^{2^{\ell}-1}}{\sqrt{d-1}},2^{\ell}\right)$

for each $(a,b)$ where $a\in\mathbb{Z}^{d-1}$ and $b\in\mathbb{Z}$. As a
result we get the infinite quadtree $\mathcal{Q}^{d}_{\infty}$ where for each
integer $\ell$ the cells of the quadtree define a subdivision of
$\mathbb{H}^{d}$.

For $x,y\in\mathbb{R}^{+}$ we define $x\bmod y=x-y\lfloor x/y\rfloor$. Chan et
al.[6] observed that shifting a quadtree by certain special vectors results in
a useful shifts also for levels with smaller cells. The following lemma was
used to define these useful shifts.

######  Lemma 3.8 (Chan et al.[6]).

Let $n>1$ be a positive odd integer, and consider the set

$X=\\{i/n\mid i=0,\dots,n-1\\}.$

Then, for any $\alpha=2^{-\ell}$, where $\ell\geq 0$ is an integer, we have
that

$X\bmod\alpha=\\{i/n\bmod\alpha\mid i=0,\dots,n-1\\}$

is equal to the set $\alpha X=\\{\alpha i/n\mid i=0,\dots,n-1\\}$.

We will look at the projection $\pi_{z}(x,z)=z$, or more precisely
$\log\pi_{z}(x,z)$. Applying $\log\pi_{z}$ to a cell $C$ gives an interval in
$\mathbb{R}$, which we will refer to as the _$z$ -range_ of $C$. We can also
apply $\log\pi_{z}$ to the quadtree as a whole and merge all nodes that have
the same $z$-range. A cell $R(x,z,w,h)$ has $z$-range $[\log z,\log z+h)$ and
by construction its children can only have $z$-range $\left[\log z,\log
z+\frac{h}{2}\right)$ or $\left[\log z+\frac{h}{2},\log z+h\right)$. Thus, we
have a tree of intervals where splitting an interval in the middle gives its
two children. This is exactly the structure of a one-dimensional Euclidean
quadtree. Additionally,
$\log\pi_{z}(T_{\sigma,\tau}(p))=\log\sigma+\log\pi_{z}(p)$, meaning that
shifts are an isometry we can apply to this one-dimensional quadtree. This
lets us use the following lemma:

######  Lemma 3.9.

Let $\mathcal{T}$ be a one-dimensional Euclidean quadtree whose largest cell
is $[0,2)$. For any two points $p,q\in[0,1)$, there is a shift
$\sigma\in\\{0,\frac{1}{3},\frac{2}{3}\\}$ such that when added to the
quadtree $p+\sigma$ and $q+\sigma$ are contained in a cell of $\mathcal{T}$
with length $<3|p-q|$ and one of the points is in the lower $\frac{1}{3}$ of
the cell.

######  Proof 3.10.

Let $\alpha=2^{-\ell}$ for some $\ell\in\mathbb{N}_{0}$ such that
$\alpha/2<|p-q|\leq\alpha$. We apply Lemma 3.8 for $n=3$ and $\alpha$: as a
consequence, a cell of size $\alpha$ can be thought of as being shifted by one
of $\\{0,\frac{\alpha}{3},\frac{2\alpha}{3}\\}$. These shifts divide the space
into intervals of length $\frac{\alpha}{3}$ where any three adjacent intervals
will make up the cell of the quadtree under some shift. Thus, $p$ and $q$ will
always be contained in a cell with length $\alpha$ when
$|p-q|\leq\frac{2\alpha}{3}$. When $|p-q|>\frac{2\alpha}{3}$, we still know
$|p-q|\leq\alpha\leq\frac{4\alpha}{3}$ so they must still be contained in a
cell $C$ with length $2\alpha$. Thus, in the worst case, $C$ has length
$2\alpha<3|p-q|$. If $C$ has $p$ and $q$ both in its higher $\frac{2}{3}$,
then the quadtree shifted by $\frac{\alpha}{3}$ or $\frac{2\alpha}{3}$ will
contain a cell $C^{\prime}$ of the same level as $C$ with the desired
property.

Now we will consider all cells with some given $z$-range and apply the
transformation $\tilde{\pi}_{x}(x,z)=x\sqrt{d-1}$. This produces a grid in
$\mathbb{R}^{d-1}$ where the cells have some power of two as the side length.
We again have access to shifts as an isometry, because
$\tilde{\pi}_{x}(T_{\sigma,\tau}(p))=\tau\sqrt{d-1}+\sigma\cdot\tilde{\pi}_{x}(p)$.
This combination lets us use a lemma due Chan [5] about _$\delta$
-centrality_. We say that a point is _$\delta$ -central_ in an axis-parallel
hypercube of side length $r$ when its Euclidean distance to the cell boundary
is at least $\delta r$.

######  Lemma 3.11 (Chan [5]).

Suppose $d$ is even. Let $v^{(j)}=(j/(d+1),\dots,j/(d+1))\in\mathbb{R}^{d}$.
For any point $p\in\mathbb{R}^{d}$ and $r=2^{-\ell}\ (\ell\in\mathbb{N})$,
there exists $j\in\\{0,1,\dots,d\\}$ such that $p+v^{(j)}$ is
$(1/(2d+2))$-central in its hypercube with side length $r$.

Using the behaviour under projections we can now also say something about the
behaviour of the hyperbolic quadtree itself.

See 1.1

######  Proof 3.12.

Let $L\in\mathbb{N}$ be such that the sphere with radius $\Delta$ can be
covered by a cube-based horobox with width $W=\frac{2^{2^{L}-1}}{\sqrt{d-1}}$
and height $H=2^{L}$. Let $D$ be $d$ rounded down to the nearest even number,
i.e. $D=2\lfloor d/2\rfloor$. For each combination of $i\in\\{0,1,2\\}$ and
$j\in\\{0,\dots,D\\}$ we define the quadtree
$\mathcal{Q}_{ij}=T_{\sigma_{i},\tau_{j}}^{-1}(\mathcal{Q}^{d}_{\infty})$,
with $\sigma_{i}=2^{H\cdot i/3}$ and $\tau_{j}=(W\cdot j/(D+1),\dots,W\cdot
j/(D+1))$. In the proof we will apply $T_{\sigma_{i},\tau_{j}}$ to all points
in $\mathcal{Q}_{ij}$ instead of transforming the cells of the quadtree
itself, but this has the same effect.

Let $p,q$ be arbitrary points with $\dist_{\mathbb{H}^{d}}(p,q)\leq\Delta$.
Lemma 3.9 gives a $\sigma_{i}$ such that $\log\pi_{z}(T_{\sigma_{i},\tau}(p))$
and $\log\pi_{z}(T_{\sigma_{i},\tau}(q))$ are contained in a cell with length
less than $3|\log\pi_{z}(p)-\log\pi_{z}(q)|$, regardless of the value of
$\tau$. This corresponds to $T_{\sigma_{i},\tau}(p)$ and
$T_{\sigma_{i},\tau}(q)$ being contained in a $z$-range with the same length.
One of $\log\pi_{z}(T_{\sigma_{i},\tau}(p))$ and
$\log\pi_{z}(T_{\sigma_{i},\tau}(q))$ is in the lower $\frac{1}{3}$ of this
$z$-range; without loss of generality we assume this is $p$.

We now look at the $d$-dimensional cell $p$ itself lies in. Without loss of
generality, we can assume this cell is $R(0,1,w,h)$ for some $w,h$. Let
$(x,z)=T_{\sigma_{i},\tau_{j}}(p)$ and $H$ denote the hyperplane $x_{1}=0$. To
get the minimum distance from $(x,z)$ to another cell with the same $z$-range,
we can now consider the minimum distance between $(x,z)$ and $H$. By Lemma 2.1
$d((x,z),H)=\arsinh\frac{|x_{1}|}{z}$, which is minimised when $x_{1}$ is
minimal and $z$ is maximal. According to Lemma 3.11, there is a $\tau_{j}$
such that $\tilde{\pi}_{x}(T_{\sigma_{i},\tau_{j}}(p))$ is
$\frac{1}{2D+2}$-central in its $(d-1)$-dimensional cell. Thus,
$x_{1}\geq\frac{w}{2D+2}$. Additionally
$\log\pi_{z}(T_{\sigma_{i},\tau_{j}}(p))$ is in the lower $\frac{1}{3}$ of its
one-dimensional cell, thus $z\leq 2^{h/3}$. This makes the distance at most
$\arsinh\left(\frac{w}{(2D+2)2^{h/3}}\right)$. Let $\ell$ be the level of the
smallest cell containing $p$ and $q$. If the level-$\ell$ cells containing $p$
and $q$ have the same $z$-range and
$\dist_{\mathbb{H}^{d}}(p,q)\leq\arsinh\left(\frac{w}{(2D+2)2^{h/3}}\right)$
with $w,h$ given by level $\ell$, they must be together in a cell of level
$\ell$. We define $f_{d}(\ell)$ as an upper bound on the ratio between the
cell’s diameter and $\dist_{\mathbb{H}^{d}}(p,q)$.

We first consider $\ell\geq 0$, where by Lemma 3.4 the diameter is
$2\arsinh\left(2^{2^{\ell}-2}\right)$ and
$w=\frac{2^{2^{\ell}-1}}{\sqrt{d-1}}$, so this distance is
$\arsinh\left(\frac{\sqrt[3]{2^{2^{\ell+1}}}}{4(D+1){\sqrt{d-1}}}\right)$.
Thus,

$f_{d}(\ell)=\frac{2\arsinh\left(2^{2^{\ell}-2}\right)}{\arsinh\left(\frac{\sqrt[3]{2^{2^{\ell}}}}{4(D+1){\sqrt{d-1}}}\right)}\leq\frac{2\ln\left(2^{2^{\ell}-1}\right)+2\arsinh{\frac{1}{2}}}{\arsinh\left(\frac{\sqrt[3]{2^{2^{\ell}}}}{4(D+1){\sqrt{d-1}}}\right)},$

To bound this further, we let
$\alpha=\frac{\sqrt[3]{2^{2^{\ell}}}}{4(D+1){\sqrt{d-1}}}$ and first assume
$\alpha\geq 2$. This means
$2^{2^{\ell}}=\mathcal{O}{\left(\alpha^{3}d^{\frac{9}{2}}\right)}$. We always
have $\arsinh\alpha\geq\ln 2\alpha>0$, so

$f_{d}(\ell)=\mathcal{O}{\left(\frac{\log\left(\alpha^{3}d^{\frac{9}{2}}\right)}{\arsinh\alpha}\right)}=\mathcal{O}{\left(\frac{\log\alpha+\log
d}{\log\alpha}\right)}=\mathcal{O}{\left(\log d\right)}.$

When we instead assume $\alpha<2$, then $\arsinh\alpha\geq\frac{\arsinh
2}{2}\cdot\alpha$ and

$f_{d}(\ell)=\mathcal{O}{\left(\frac{2\log\left(2^{2^{\ell}-2}\right)}{\frac{\sqrt[3]{2^{2^{\ell}}}}{4(D+1){\sqrt{d-1}}}}\right)}=\mathcal{O}{\left(\frac{2^{\ell}d\sqrt{d}}{\sqrt[3]{2^{2^{\ell}}}}\right)}=\mathcal{O}{\left(d\sqrt{d}\right)}.$

For $\ell<0$, Lemma 3.2 implies that the width is at least
$\frac{\frac{1}{2}\cdot 2^{\ell}}{\sqrt{d-1}}$, the height is at most $1$, and
the diameter is at most
$2\arsinh\left(\frac{1}{2}\sqrt{\frac{4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}\right)$.
Finally, we use that $\arsinh x\leq x$ for any $x$ and
$\arsinh{x}=\Omega\left(x\right)$ for bounded $x$:

$f_{d}(\ell)\leq\frac{2\arsinh\left(\frac{1}{2}\sqrt{\frac{4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}\right)}{\arsinh\left(\frac{\frac{1}{2}\cdot
2^{\ell}}{(2D+2)\sqrt[3]{2}\sqrt{d-1}}\right)}=\mathcal{O}{\left(\frac{\sqrt{\frac{4^{\ell}+(2^{2^{\ell}}-1)^{2}}{2^{2^{\ell}}}}}{\frac{2^{\ell}}{d\sqrt{d}}}\right)}=\mathcal{O}{\left(d\sqrt{d}\right)}.\qedhere$

###  3.3 L-order

When we have the Euclidean quadtree for a set of points, we can do a depth-
first traversal of the tree and note in which order the points are visited.
This gives rise to the Z-order. As it turns out, adding or removing points
does not change the Z-order and for a pair of points we can determine which
comes first without ever constructing a quadtree. The only thing to specify is
which infinite quadtree their quadtree would be a subset of, because a
differently shifted quadtree can give different results.

We can do the same to get the L-order from a hyperbolic quadtree. Here, we
first need to define how exactly we do the depth-first traversal. For levels
$\ell>0$, we first visit the top child and then visit the bottom children in
Z-order. For lower levels, the split is the same as for Euclidean quadtrees so
we visit the children in the same order as the Z-order.

######  Lemma 3.13.

For two points $p,p^{\prime}\in\mathbb{H}^{d}$, we can check which comes first
in the L-order for $\mathcal{Q}^{d}_{\infty}$ by using
$\mathcal{O}{\left(d\right)}$ floor, logarithm, bitwise logical and standard
arithmetic operations.

######  Proof 3.14.

To compare $p$ and $p^{\prime}$, we first define
$\tilde{\pi}(p)=(\tilde{\pi}_{x}(p),\log\pi_{z}(p))$, then let
$(x,z)=\tilde{\pi}(p)$ and $(x^{\prime},z^{\prime})=\tilde{\pi}(p^{\prime})$
for convenience. We then check if both $\lfloor x/2^{z}\rfloor=\lfloor
x^{\prime}/2^{z^{\prime}}\rfloor$ and $\lfloor z\rfloor=\lfloor
z^{\prime}\rfloor$. If that is the case, the points are in the same level-$0$
cell. Thus, under $\tilde{\pi}$ they are in a $d$-dimensional Euclidean
quadtree and we can use the Z-order of $(x,z)$ and $(x^{\prime},z^{\prime})$
to determine which comes first.

Otherwise, we need to look at the situation at the highest level $\ell$ where
$p$ and $p^{\prime}$ are in different cells. If one of the points is in the
top child cell of its parent, that point comes first. If both are in one of
the bottom child cells, then we look at which of the cells comes first in the
Z-order. We can distinguish these cases by checking if $p$ and $p^{\prime}$
are in cells of the same $z$-range at level $\ell$.

Let $L(a,b)=1+\lfloor\log(a\oplus b)\rfloor$ give the smallest index such that
all bits of index at least $L(a,b)$ in the binary representations of $a$ and
$b$ match (where $\oplus$ denotes bitwise exclusive-or). At some level $\ell$,
the points $p$ and $p^{\prime}$ are in cells of the same $z$-range if $\lfloor
z/2^{\ell}\rfloor=\lfloor z^{\prime}/2^{\ell}\rfloor$. In other words, their
binary expansions match for the bits of index at least $\ell$, meaning
$L(z,z^{\prime})$ is the smallest value of $\ell$ for which this holds. Under
the $\log\pi_{z}$ projection this $z$-range starts at the nearest multiple of
$2^{L(z,z^{\prime})}$ below $z$, which is $\lfloor
z/2^{L(z,z^{\prime})}\rfloor\cdot 2^{L(z,z^{\prime})}$. Without the projection
this becomes $2^{\lfloor z/2^{L(z,z^{\prime})}\rfloor\cdot
2^{L(z,z^{\prime})}}$. We can now look at the cells with this $z$-range. As
noted in Section 3.2, under $\tilde{\pi}_{x}$ these cells form a
$(d-1)$-dimensional Euclidean grid. The side length is $\sqrt{d-1}$ times the
Euclidean width of the original horobox cells, which is by definition their
width multiplied by their $z$-coordinate and thus

$2^{\lfloor z/2^{L(z,z^{\prime})}\rfloor\cdot
2^{L(z,z^{\prime})}}\cdot\frac{2^{2^{L(z,z^{\prime})}-1}}{\sqrt{d-1}}.$

We can rewrite this as $\frac{2^{L^{*}}}{\sqrt{d-1}}$ with $L^{*}=\lfloor
z/2^{L(z,z^{\prime})}\rfloor\cdot 2^{L(z,z^{\prime})}+2^{L(z,z^{\prime})}-1$.
Thus, $p$ and $p^{\prime}$ will be in the same level $L(z,z^{\prime})$ cell if
for all $i=1,\dots,d-1$ we have $\lfloor x_{i}/2^{L^{*}}\rfloor=\lfloor
x_{i}^{\prime}/2^{L^{*}}\rfloor$ or equivalently $L(x_{i},x_{i}^{\prime})\leq
L^{*}$.

This check lets us know if $p$ and $p^{\prime}$ are already in the same cell
at level $L(z,z^{\prime})$. If they are, then they were first split with a
horosphere normal to the $z$ axis. We can thus determine their L-order by
simply checking if $z<z^{\prime}$. Otherwise, they were split first with some
hyperplane normal to some $x_{i}$-axis for some $i\in 1,\dots,d-1$, thus we
can find which of $p$ or $p^{\prime}$ comes first by determining the
$d-1$-dimensional Euclidean Z-order of $x$ and $x^{\prime}$.

##  4 Applications

Theorem 1.1 and Lemma 3.13 are equivalent to statements about Euclidean
quadtrees Chan et al.[6] use to find an approximate nearest neighbour and
closest pair, so we can do the same in hyperbolic space. For both problems the
algorithm is similar. Given a point set $P$, we first make $3d+3$ self-
balancing binary search trees (e.g. red-black tree [7]) where each sorts the
points based on the L-order from one of the infinite quadtrees from Theorem
1.1. By Lemma 3.13 this takes $\mathcal{O}{\left(d^{2}n\log n\right)}$ time.
Notice that we can add or remove a point in all of these trees in
$\mathcal{O}{\left(d^{2}\log n\right)}$ time.

To get the nearest neighbour of some point $p$, we determine where it would
end up in the L-order for each of the trees, then return $q$; the closest of
the neighbours. This takes $\mathcal{O}{\left(d^{2}\log n\right)}$ time and
gives an $\mathcal{O}{\left(d\sqrt{d}\right)}$-approximate nearest neighbour:
the actual nearest neighbour $q^{\prime}$ of $p$ will be in the smallest cell
$p$ is in. Because the returned point $q$ was closer to $p$ in the L-order
than $q^{\prime}$, it must also be in that cell. By Theorem 1.1 this means it
can be at most $\mathcal{O}{\left(d\sqrt{d}\right)}$ times further away,
making it an $\mathcal{O}{\left(d\sqrt{d}\right)}$-approximate nearest
neighbour.

The same reasoning can be used to get an
$\mathcal{O}{\left(d\sqrt{d}\right)}$-approximate closest pair. To find an
approximate closest pair we go through the sorted lists and return the pair of
neighbouring points that is closest. This takes
$\mathcal{O}{\left(d^{2}n\right)}$ time. The above reasoning yields the
following theorem.

See 1.2

## References

  * [1] Srinivas Aluru.  Quadtrees and octrees.  In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004.  https://doi.org/10.1201/9781420035179.ch19 doi:10.1201/9781420035179.ch19.
  * [2] Riccardo Benedetti and Carlo Petronio.  Lectures on Hyperbolic Geometry.  Springer Science & Business Media, 1992.
  * [3] Károly Böröczky.  Gömbkitöltések állandó görbületű terekben I.  Matematikai Lapok (in Hungarian), 25(3-4):265–306, 1974.
  * [4] James W Cannon, William J Floyd, Richard Kenyon, Walter R Parry, et al.  Hyperbolic geometry.  Flavors of Geometry, 31(59-115):2, 1997.
  * [5] Timothy M. Chan.  Approximate nearest neighbor queries revisited.  Discrete & Computational Geometry, 20(3):359–373, Oct 1998.  https://doi.org/10.1007/PL00009390 doi:10.1007/PL00009390.
  * [6] Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones.  On locality-sensitive orderings and their applications.  SIAM Journal on Computing, 49(3):583–600, 2020.  https://doi.org/10.1137/19M1246493 doi:10.1137/19M1246493.
  * [7] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to Algorithms, Second Edition.  The MIT Press and McGraw-Hill Book Company, 2001.
  * [8] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars.  Computational geometry: algorithms and applications, 3rd Edition.  Springer, 2008.  URL: https://www.worldcat.org/oclc/227584184.
  * [9] Raphael A. Finkel and Jon Louis Bentley.  Quad trees: A data structure for retrieval on composite keys.  Acta Informatica, 4:1–9, 1974.  https://doi.org/10.1007/BF00288933 doi:10.1007/BF00288933.
  * [10] Sariel Har-peled.  Geometric Approximation Algorithms.  American Mathematical Society, USA, 2011.
  * [11] Birger Iversen.  Hyperbolic geometry.  Number 25. Cambridge University Press, 1992.
  * [12] Robert Krauthgamer and James R. Lee.  Navigating nets: simple algorithms for proximity search.  In J. Ian Munro, editor, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 798–807. SIAM, 2004.  URL: http://dl.acm.org/citation.cfm?id=982792.982913.
  * [13] Robert Krauthgamer and James R. Lee.  Algorithms on negatively curved spaces.  In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 119–132. IEEE Computer Society, 2006.  https://doi.org/10.1109/FOCS.2006.9 doi:10.1109/FOCS.2006.9.
  * [14] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná.  Hyperbolic geometry of complex networks.  Physical Review E, 82(3):036106, 2010.
  * [15] John Lamping, Ramana Rao, and Peter Pirolli.  A focus+ context technique based on hyperbolic geometry for visualizing large hierarchies.  In Proceedings of the SIGCHI conference on Human factors in computing systems, pages 401–408, 1995.
  * [16] Maximilian Nickel and Douwe Kiela.  Learning continuous hierarchies in the lorentz model of hyperbolic geometry.  In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3776–3785. PMLR, 2018\.  URL: http://proceedings.mlr.press/v80/nickel18a.html.
  * [17] William P Thurston.  Three dimensional manifolds, kleinian groups and hyperbolic geometry.  Bulletin (New Series) of the american mathematical society, 6(3):357–381, 1982.
  * [18] William P Thurston.  Three-dimensional geometry and topology, volume 1.  Princeton Mathematical Series, Vol. 35, 1997.
  * [19] Abraham A Ungar.  Einstein’s special relativity: The hyperbolic geometric viewpoint.  arXiv preprint arXiv:1302.6961, 2013.
  * [20] Xian Wu and Moses Charikar.  Nearest neighbor search for hyperbolic embeddings.  CoRR, abs/2009.00836, 2020.  URL: https://arxiv.org/abs/2009.00836, http://arxiv.org/abs/2009.00836 arXiv:2009.00836.