Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces

Before stating the new contribution, let us first examine why the ideas behind the existing Steiner spanner constructions in ${ℍ}^d$ are insufficient to get optimal sparsity. First, the Steiner spanner of Krauthgamer and Lee [42] considers a more general setting than ${ℍ}^d$, which among other things means they get a dependence on the local doubling dimension and consequently dependencies on $d$ will always be of the form $𝒪\left(d\right)$. Since we care about the exact constants in the exponent of $\epsilon$, this makes it unsuitable. Kisfaludi-Bak and Van Wordragen [38] place Steiner points at distance $\epsilon$ in a $d$-dimensional volume, which naturally gives a dependence ${\epsilon }^{-d}$. It is not obvious how one can place Steiner points only at distance $\sqrt{\epsilon }$ and along $(d-1)$-dimensional boundaries to get the optimal dependence ${\epsilon }^{(1-d)/2}$. Moreover, they never have edges between two Steiner points (giving a “bipartite” Steiner spanner) and we show in Lemma 10 that such edges are necessary to get a Steiner spanner with optimal sparsity. Finally, Park and Vigneron [51] give a Steiner spanner with additive error $𝒪\left(\log d\right)$, which is good for large distances but does not help with the most challenging regime of distances between $1$ and $\frac{1}{\epsilon }$.

Our main contribution is the following theorem.

Our edge count nearly matches the lower bound $\mathrm{\Omega }\left({\epsilon }^{(1-d)/2}n\right)$ given by Bhore and Tóth [6] for Euclidean Steiner spanners, up to the factor $\log \frac{1}{\epsilon }$. Our ${𝒪}_d$ notation hides a factor of $d^{𝒪\left(d\right)}$. Note that the Euclidean lower bound is also a valid lower bound in ${𝕊}^d$ and ${ℍ}^d$, as both spaces are locally Euclidean, meaning that any hard instance in ${𝔼}^d$ can be embedded both in ${𝕊}^d$ and ${ℍ}^d$ with arbitrarily small distortion.

Thus, we nearly settle Question 1 in the three geometries cases of constant dimension, up to the $\log 1/\epsilon$ term. In Euclidean space our edge count matches a recent result of Chang et al. [17], however, our technique is completely different and arguably simpler. The main advantage is that our spanner can be maintained dynamically when points are added to $P$ or deleted from $P$, using ${𝒪}_{d,\epsilon }(\log n)$ time updates. As a result of the dynamicity and the simple structure, our spanner can readily act as a data structure for classic query problems such as dynamic approximate nearest neighbours and (dynamic approximate) bichromatic closest pair. From the Steiner spanner constructions, one can also directly get (dynamic) Steiner tree covers of size ${𝒪}_d\left({\epsilon }^{(1-d)/2}\log \frac{1}{\epsilon }\right)$, which generalise the result of [17].

The main challenge in establishing Theorem 1 lies in the hyperbolic variant. While our spanner for ${𝕊}^d$ can be relatively easily derived from our Euclidean construction using geometric transformations, our spanner for ${ℍ}^d$ is substantially different. In our approach, we use Euclidean (doubling space) ideas for small distances and tree-based ideas (constant-additive spanner) for sufficiently large distances, but in the hyperbolic setting, this leaves a gap for point pairs at distances between $1$ and $\frac{1}{\epsilon }$. This is the most challenging regime and requires mixing ideas from both approaches, as well as new ideas. As a result, we obtain a significantly smaller hyperbolic Steiner spanner compared to the state of the art, which had size ${𝒪}_d({\epsilon }^{-d}\log (1/\epsilon )n)$ [38].

Note that the spanners of Theorem 1 are bipartite in case of ${𝔼}^d$ and ${𝕊}^d$, and we are also able to design bipartite Steiner spanners in ${ℍ}^d$ for any $d\ge 3$ with the same properties as stated in Theorem 1. Surprisingly, we prove that a bipartite Steiner spanner of size $o(n/\epsilon )$ does not exist in ${ℍ}^2$. As a corollary of this lower bound, we obtain an $\mathrm{\Omega }(n\log n)$ lower bound for the edge count of a hyperbolic (non-Steiner) $2$-spanner in the plane. We prove that there exist $2$-spanners in ${ℍ}^d$ of size ${𝒪}_d(n\log n)$, matching our lower bound, and settling Question 2.

By incorporating so-called transitive closure spanners [55] on certain trees obtained from hyperbolic quadtrees, we are also able to get Steiner spanners with $\epsilon$ additive error for any $\epsilon >0$ whose size is very close to linear in $n$: it has size ${𝒪}_{\epsilon ,d}(n\log \alpha (n))$, where $\alpha$ is the inverse Ackermann function.

While no direct lower bounds are known for additive hyperbolic spanners, this stronger variant of an additive spanner is in stark contrast with the Euclidean setting where no subquadratic-size additive (Steiner) spanners can exist: indeed, in the Euclidean case one can scale any point set, so a scale-invariant spanner construction cannot give constant additive error. In the hyperbolic setting, no scaling transformation exists, and the thin triangle property [32] allows the construction of Steiner spanners with constant additive error. In terms of Question 3, this is further evidence that pairwise distant points in ${ℍ}^d$ are structurally simpler than their Euclidean counterparts. It is an interesting open question whether one can improve the edge count by removing the $\log \alpha (n)$ term from the bound of Theorem 3.

Finally, we apply our spanners to two different problems. First, we observe that our spanner construction easily extends to certain closed Riemannian manifolds of constant curvature: in particular, closed constant-curvature orientable surfaces and higher-dimensional manifolds obtained as a quotient of the three base geometries using a finite isometry group.

Next, we demonstrate the usefulness of our spanners by establishing dynamic data structures for approximate nearest neighbours (ANN) and bichromatic closest pair. Hyperbolic ANN algorithms have already been proposed and implemented, albeit without worst-case guarantees on the running time [63, 53]. In the $(1+\epsilon )$-approximate bichromatic closest pair problem, we are given two point sets $R$ and $B$ and wish to find a pair $(r,b)\in R\times B$ whose distance is at most $1+\epsilon$ more than that of the closest pair between $R$ and $B$. The dynamic version requires that the approximate bichromatic closest pair can be recalculated efficiently after point insertions and removals in $R$ and $B$. Here, we improve over the result of [29] in Euclidean space, which uses ${𝒪}_d\left({\epsilon }^{1-d}\log (1/\epsilon )n\right)$ space and handles updates in ${𝒪}_d\left({\epsilon }^{1-d}\log (1/\epsilon )\log n\right)$ time, with a data structure that uses ${𝒪}_d\left({\epsilon }^{(1-d)/2}\log (1/\epsilon )n\right)$ space and handles updates in ${𝒪}_d\left({\epsilon }^{(1-d)/2}\log (1/\epsilon )\log n\right)$ time. We also improve on the result of [38] in hyperbolic space, where the factors ${\epsilon }^{-d}$ are improved to ${\epsilon }^{(1-d)/2}$ in both the running time and space usage bounds. To the best of our knowledge we give the first data structure for approximate bichromatic closest pair that is explicitly for spherical space. We obtain analogous improvements compared to the state of the art for (dynamic) ANN in hyperbolic and spherical space.

Complete details are available in the full version; we give abridged preliminaries in Section 2 and an overview of the main ideas and constructions in Section 3. Finally, Section 4 concludes the paper by proposing some intriguing open problems.

In this paper we use the half-space model of hyperbolic geometry (for more details, refer to for example [11] or the textbooks [34, 61, 4]). This assigns any point $p\in {ℍ}^d$ coordinates $(x(p),z(p))\in {ℝ}^{d-1}\times {ℝ}_{>0}$ in the upper half-space, which also lets us refer to the positive $z$-direction as “up”. Important to note is that hyperbolic distances are not given by the Euclidean distances in the model, which also means that the shortest curve $pq$ between points $p,q\in {ℍ}^d$ is often not a Euclidean segment. In general, $pq$ is modelled by an arc from a Euclidean circle perpendicular to the Euclidean hyperplane $z=0$ (in particular its centre lies at $z=0$) and $pq$ has hyperbolic length

but if $x(p)=x(q)$ then $pq$ is a vertical Euclidean line segment and $|pq|=\left|\ln \frac{z(p)}{z(q)}\right|$. Note here that applying any isometry of ${𝔼}^{d-1}$ to $x(p)$ and $x(q)$ yields the same distance, as does multiplying all of $x(p),x(q),z(p)$ and $z(q)$ by the same positive factor. Vertical Euclidean hyperplanes are also hyperbolic hyperplanes (as with vertical segments), but horizontal ones are not. These are horospheres, but we will not directly use any property of horospheres other than them being distinct from hyperplanes.

Here we describe the quadtree of [38] while introducing new notation that will be useful throughout this paper. Instead of being based on hypercubes, its cells are cube-based horoboxes. In the half-space model, a cube-based horobox $C$ is a Euclidean axis-parallel box with corners $(x_{\min }(C),z^{\downarrow }(C))$ and $(x_{\max }(C),z^{\uparrow }(C))$ with its width given by $\frac{x_{\max }(C)-x_{\min }(C)}{z^{\downarrow }(C)}=(w(C),\mathrm{\dots },w(C))$ and height $h(C)=\log \frac{z^{\uparrow }(C)}{z^{\downarrow }(C)}$. This definition ensures that any two cube-based horoboxes with the same width and height are isometric. Just like any box can tile Euclidean space, any horobox can tile hyperbolic space.

Instead of being based on the grid (the tiling of ${𝔼}^d$ with isometric hypercubes) like the Euclidean quadtree, the hyperbolic quadtree is based on the binary tiling. To construct a binary tiling, we start with the cube-based horobox $C$ with $x_{\min }(C)=(0,\mathrm{\dots },0)$, $z^{\downarrow }(C)=1$, $w(C)=\frac{1}{\sqrt{d-1}}$ and $h(C)=1$. Now we apply the isometry $T_{\sigma ,\tau }(x,z)=\sigma \cdot (x+\tau ,z)$ for all values $\tau =a/\sqrt{d-1}$ with $a\in {\mathbb{Z}}^{d-1}$ and $\sigma =2^b$ with $b\in \mathbb{Z}$. This gives a tiling that covers all of ${ℍ}^d$ with isometric tiles; see Figure 1. Note that the two-dimensional tiling resembles a binary tree, hence the name. In general the $d$-dimensional tiling bears resemblance to a $(d-1)$-dimensional Euclidean quadtree, where each “layer” of the tiling at a fixed $z$ value is a level of this quadtree.

We formalise this tree structure by thinking of the binary tiling as the infinite arborescence $T^0$, which has the tiles as its vertices and a directed edge from any tile to the tile directly above it. We can then also generalise this to $T^{\mathrm{\ell }}$ for $\mathrm{\ell }\in \mathbb{N}$. The tiling for $T^{\mathrm{\ell }}$ is constructed by taking the cube-based horobox $C$ with again $x_{\min }(C)=(0,\mathrm{\dots },0)$ and $z^{\downarrow }(C)=1$, but now $w(C)=2^{2^{\mathrm{\ell }}-1}/\sqrt{d-1}$ and $h(C)=2^{\mathrm{\ell }}$. Then, we apply $T_{\sigma ,\tau }$ for all values $\tau =a\cdot w(C)$ with $a\in {\mathbb{Z}}^{d-1}$ and $\sigma =2^{b\cdot h(C)}$ with $b\in \mathbb{Z}$. The arborescence $T^{\mathrm{\ell }}$ follows as before, where it is worth noting that the in-degree of vertices of $T^{\mathrm{\ell }}$ has grown from $2^{d-1}$ to $2^{(d-1)\cdot 2^{\mathrm{\ell }}}$.

The tiles are chosen exactly so that each tile of $T^{\mathrm{\ell }+1}$ is the union of a tile of $T^{\mathrm{\ell }}$ with its children. Thus, the tilings for $T^{\mathrm{\ell }}$ can be used to define the hyperbolic quadtree for levels $\mathrm{\ell }\ge 0$. Levels are now constructed by splitting each cell at level $\mathrm{\ell }+1$ up with a Euclidean quadtree split. See Figure 2 for an illustration.

Since we will make frequent use of trees and arborescences, we also introduce some related notation for an arbitrary tree or arborescence of cells $T$. Given two cells $C,C^{\prime }\in V(T)$, we let $\mathrm{lca}(C,C^{\prime },T)$ denote their lowest common ancestor in $T$. Given a point $p\in {ℍ}^d$, we let $\mathrm{cell}(p,T)$ denote the cell of $T$ containing $p$, and given a second point $q\in {ℍ}^d$ we use the shorthand $\mathrm{lca}(p,q,T)=\mathrm{lca}(\mathrm{cell}(p,T),\mathrm{cell}(q,T),T)$.

Our first challenge here is that for super-constant hyperbolic distances the hyperbolic quadtree gets meaningfully different from a Euclidean quadtree. This was already dealt with to get a bipartite Steiner spanner in [38], but we need new insights to get near-optimal dependence on $\epsilon$. The results that made the construction for small distances work are not enough, as the exponential expansion of hyperbolic space causes them to break down. In particular, Lemma 4 is false for super-constant hyperbolic distances: as the distances grow the hyperbolic Pythagorean theorem converges to the triangle inequality, which precludes us from proving something stronger for large hyperbolic distances. At medium hyperbolic distances (between $1$ and $1/\epsilon$), we give a result reminiscent of Lemma 4 to enable dependences ${\epsilon }^{(1-d)/2}$ instead of ${\epsilon }^{1-d}$.

Note that when $|pq|=\mathrm{\Theta }\left(1\right)$ and $\delta =\sqrt{\epsilon }|pq|$ this is very similar to Lemma 4, while when $|pq|=\mathrm{\Theta }\left(1/\epsilon \right)$ and $\delta =\epsilon |pq|$ we get the same guarantee as from the triangle inequality; the most interesting regime of the lemma is in between these two values. The hyperbolic bipartite Steiner spanner now follows from a similar construction as the one for smaller distances, with two major changes. First, we replace Lemma 4 with Lemma 7. Second, we only connect each point to its “ancestors” in the tiling (here one should think of ancestors in the binary tree), as opposed to all tiles, because in the hyperbolic quadtree there can be unboundedly many sibling tiles inside a parent cell. With this Steiner spanner we can prove Theorem 1 for all cases except for super-constant distances in ${ℍ}^2$.

The coming lower bound shows that, surprisingly, having a weaker result for specifically ${ℍ}^2$ is unavoidable unless we go for a very different, non-bipartite construction. First, Observation 9 gives a simple alternative procedure to turn a bipartite Steiner spanner into a spanner without Steiner points (as already observed by [38]). The procedure maintains the same edge bound, but in the worst case it doubles the stretch from $(1+\epsilon )$ to $2+2\epsilon$. As a result, we improve the $(2+\epsilon )$-spanner of [38], but perhaps more importantly it lets us apply the coming spanner lower bound to bipartite Steiner spanners. Moreover, we will later use the same strategy to make a (non-Steiner) $2$-spanner.

For the lower bound, we show that a $(2+\frac{1}{\ln n})$-spanner for a set of $n$ evenly spaced points on a circle of radius $3\ln n$ already requires $\mathrm{\Omega }\left(n\log n\right)$ edges. This implies three things for these point sets:

• $\mathrm{■}$

  a $(2+\epsilon )$-spanner needs $\mathrm{\Omega }\left(n/\epsilon \right)$ edges,

• $\mathrm{■}$

  a bipartite Steiner $(1+\epsilon )$-spanner needs $\mathrm{\Omega }\left(n/\epsilon \right)$ edges (through Observation 9), and

• $\mathrm{■}$

  a $2$-spanner needs $\mathrm{\Omega }\left(n\log n\right)$ edges.

First of all, the smallest and largest distance among the points differ only by a multiplicative factor close to $\frac{3}{2}$, which lets us conclude that the path between any two points $p$ and $q$ in the $(2+\frac{1}{\ln n})$-spanner can have at most $2$ hops. We denote by $m$ the middle vertex of the $2$-hop path. Next, we observe that the location of $m$ is highly constrained: the number of points on the circle separating $m$ from $p$ and $q$ must be at most a constant times larger than the number of points separating $p$ from $q$. This observation lets us partition all pairs of points into classes based on the number of points separating them, of the form $[{51}^i,{51}^{i+1})$. We prove that for any pair of points, the longer edge on the path connecting them can only be shared with one disjoint pair of the same class. Thus, we require $\mathrm{\Theta }\left(n\right)$ edges per class, and get the $\mathrm{\Omega }\left(n\log n\right)$ lower bound from having $\mathrm{\Theta }\left(\log n\right)$ classes. $◀$

To bypass the lower bound, we then work towards a non-bipartite Steiner spanner (i.e., one where Steiner points can be connected to Steiner points). The key to making this spanner work is to make use of the exponential divergence of lines in hyperbolic space: two long segments whose endpoints lie close together get exponentially close near their middle. We capture this property in Lemma 11.

Directly from Lemma 11, we get Lemma 12 which gives a quasi-isometric embedding of any hyperbolic point set into a union of $𝒪\left(d\right)$ trees, similar to the much more involved quasi-isometric embedding of any hyperbolic metric space into a product of $d$ trees [8, 9]. For our purposes, it implies a Steiner $(1+𝒪\left(\epsilon \right))$-spanner with only $𝒪\left(dn\right)$ edges for hyperbolic point sets with minimum distance $\frac{1}{\epsilon }\log \frac{1}{\epsilon }$.

To obtain a Steiner spanner for smaller distances, we need to eliminate the additive distortion. This comes from the sharp turn at the highest node on paths in these trees. We avoid this with ideas from Theorem 8. Namely, we consider the tiling $T^{4+\log \log d}$ and connect each (input and Steiner) point from the trees of Lemma 12 to ${𝒪}_d\left({\epsilon }^{(1-d)/2}\right)$ Steiner points placed for the $2\log \frac{1}{\epsilon }$ cells above it. This gives more options for a gradual turn and with that finally proves that our main theorem Theorem 1 holds in all cases.

We can also get a Steiner spanner with additive error $\epsilon$ by using the same general idea as in Theorem 13. One of the issues here is that we accumulate some error in each hop along a spanner path, and we do not have a bound on the number of hops a spanner path might need to take. This problem can be mitigated by using the transitive closure spanner of Thorup [60] to reduce the number of hops to $𝒪\left(\alpha (n)\right)$, and get the same error no matter how (hop-)distant two points are.

We match the lower bound of Lemma 10 with a 2-spanner that has ${𝒪}_d\left(n\log n\right)$ edges (in hyperbolic space of any dimension). To get the 2-spanner, we use two ways of getting a spanner from a Steiner spanner. For small distances we can get a $(1+\epsilon )$-spanner from Theorem 6. For larger distances, we first construct a new bipartite Steiner spanner that gives constant additive error and has ${𝒪}_d\left(n\log n\right)$ edges. For this, we essentially take the trees of Lemma 12 for $\epsilon =1/d^8$, then connect each input point to $𝒪\left(\log n\right)$ nodes in each tree such that any pair of points is connected to a common node. This avoids the multiplicative distortion and makes the Steiner spanner bipartite. We then turn this into a $2$-spanner with the approach of Observation 9, but we bound the stretch more precisely using the specific geometric configuration to avoid the additive error.

We can maintain our three multiplicative Steiner spanners dynamically by using the so-called Z-order [48] or L-order [38] for each of our shifted quadtrees. These are specific orderings of the input point set based on post-order traversals of the respective quadtree, i.e., our data structure is essentially $𝒪\left(d\right)$ differently ordered lists of our $n$ input points, as seen in locality-sensitive orderings [15, 29].

Comparing two points based on such an order is equivalent to asking which comes first if we add both to a quadtree and do a depth-first traversal of it, but these comparisons can be done in $𝒪\left(d\right)$ time without explicitly computing the quadtree. The multiplicative Steiner spanner constructions are such that for any input point, the edges connected to it purely depend on its neighbours in the Z- or L-order, which allows for efficient updates.

The results below follow directly from having dynamic bipartite Steiner spanners.

Finally, we note that we also get results for specific manifolds of the form ${𝕏}^d/\mathrm{\Gamma }$ for $𝕏\in \{ℍ,𝔼,𝕊\}$, where points $p,q\in {𝕏}^d$ are unified if some isometry from $\mathrm{\Gamma }$ maps $p$ to $q$. If $\mathrm{\Gamma }$ is finite, then we simulate this by simply replacing every point $p\in P$ by $|\mathrm{\Gamma }|$ copies.

A similar approach works for constant curvature surfaces of any genus $g$ that are closed, orientable and connected, since these are always isometric to manifolds of the form ${𝕏}^2/\mathrm{\Gamma }$. Here, we use an idea from Despré, Kolbe and Teillaud [25] to represent each point in ${𝕏}^2/\mathrm{\Gamma }$ by $g^{𝒪\left(g\right)}$ points in ${𝕏}^2$.