Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree

Kisfaludi-Bak, Sándor; Odak, Saeed; Singh, Satyam; van Wordragen, Geert

doi:10.4230/LIPIcs.SoCG.2026.64

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree

Sándor Kisfaludi-Bak

Department of Computer Science, Aalto University, Espoo, Finland Saeed Odak

Department of Computer Science, Aalto University, Espoo, Finland Satyam Singh

Department of Computer Science, Aalto University, Espoo, Finland Geert van Wordragen

Department of Computer Science, Aalto University, Espoo, Finland

Abstract

We give an approximation scheme for the TSP in $d$ -dimensional hyperbolic space that has optimal dependence on $\varepsilon$ under Gap-ETH. For any fixed dimension $d\geq 2$ and for any $\varepsilon>0$ our randomized algorithm gives a $(1+\varepsilon)$ -approximation in time $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$ . We also provide an algorithm for the hyperbolic Steiner tree problem with the same running time.

Our algorithm is an Arora-style dynamic program based on a randomly shifted hierarchical decomposition. However, we introduce a new hierarchical decomposition called the hybrid hyperbolic quadtree to achieve the desired large-scale structure, which deviates significantly from the recently proposed hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen (JoCG’25). Moreover, we have a new non-uniform portal placement, and our structure theorem employs a new weighted crossing analysis. We believe that these techniques could form the basis for further developments in geometric optimization in curved spaces.

Keywords and phrases:

Hyperbolic traveling salesman problem, TSP, Hyperbolic Steiner tree problem, Approximation scheme, Banyan, Hyperbolic geometry

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry ; Theory of computation

\rightarrow

Approximation algorithms analysis

Related Version:

Full Version: https://doi.org/10.48550/arXiv.2603.09834 [32]

Funding:

This work was supported by the Research Council of Finland, Grant 363444.

DOI:

10.4230/LIPIcs.SoCG.2026.64

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The metric traveling salesman problem (TSP) is easily stated: given a set of $n$ points in some metric space, find a cyclic permutation of points that minimizes the sum of lengths between consecutive points. A very commonly studied variant is when the underlying space is $d$ -dimensional Euclidean space (henceforth denoted by $\mathbb{R}^{d}$ ), and admits $(1+\varepsilon)$ -approximations in polynomial time (PTAS) for any fixed $\varepsilon>0$ [1, 38]. The PTAS of Arora [1] for Euclidean TSP has been tirelessly improved, generalized, and optimized throughout the past decades by researchers working on geometric optimization. Today, we have Gap-ETH-tight running times in Euclidean space, and have working approximation schemes in any so-called doubling space to many related problems [3, 4, 5, 10, 31, 40, 42]. Moreover, many components of an Arora-style scheme can also be used in other important optimization problems related to network design, clustering, and facility location [2, 16, 17, 18, 20, 48, 22].

The key components of Arora’s scheme [1] involve a hierarchical decomposition of the space (a quadtree) where the space is decomposed into fat¹¹1An object (a point set) is $\alpha$ -fat if the radius of the minimum circumscribed ball divided by the radius of the maximum inscribed ball is at least $\alpha$ . It is fat if it is $\alpha$ -fat for some fixed constant $\alpha>0$ . regions called cells, each of which in turn is decomposed into $f(d)$ smaller fat cells, where $d$ is the dimension of the space. One can then argue that using small modifications, called patching on the tour, we can find a $(1+\varepsilon)$ -approximate tour that crosses between neighboring cells of the decomposition only $g(\varepsilon,d)$ times (or, in some cases, $f(\varepsilon,d)\cdot\mathrm{poly}(\log n)$ times), and these crossings come from a fixed set of points called portals. However, this argument cannot be made for a fixed hierarchical decomposition; one needs to apply a randomized decomposition and ensure that the number of crossings is small in expectation. Finally, one can employ a bottom-up dynamic programming algorithm on the hierarchy to compute partial solutions for each possible connection pattern of the cell’s portals. Crucially, the running time depends on the number of portals used by the approximate tour as well as the number of children a cell can have, as both of these terms appear in the exponent of the dynamic programming algorithm.

In the Euclidean case, the hierarchical decomposition is a quadtree whose nodes correspond to axis-aligned hypercubes whose side length is a power of $2$ . The entire quadtree is shifted randomly, ensuring that in expectation the hypercube boundaries avoid hitting many short segments of the tour.

Doubling spaces are those metric spaces where for all $r\geq 0$ it holds that all balls of radius $r$ can be covered by constantly many balls of radius $r/2$ . The above techniques have been successfully generalized to this much more general setting, where randomized net-trees and padded decompositions take over the role of randomly shifted quadtrees [12, 15, 23, 28, 36, 44].

However, generalizing beyond the doubling space setting has been difficult. A natural target of extensions into the non-doubling setting is hyperbolic space, where the local structure is (almost) Euclidean, but at super-constant scale the space expands exponentially. Moreover, the exponential expansion leads to a tree-like behavior that can be exploited algorithmically.

Geometric optimization in hyperbolic space is still in its infancy, but there is reason to believe that even low-dimensional hyperbolic space is highly relevant from the practical perspective [7, 8, 11, 24, 25, 26, 39, 41, 43, 46, 47], and establishing the basic tools of geometric optimization in this setting will be widely useful for future algorithmic developments in both theory and practice. Thus, it would be prudent to explore the following problem.

Problem 1.

Adapt algorithms from Euclidean geometric optimization to negatively curved (non-doubling) spaces, or prove lower bounds that rule out such adaptations.

Krauthgamer and Lee [35] showed the existence of a PTAS for TSP in a more general setting: in so-called geodesic, visual and Gromov-hyperbolic spaces. This implies the existence of a PTAS in $d$ -dimensional hyperbolic space (henceforth denoted by $\mathbb{H}^{d}$ ); however, the running time dependencies on $d$ and $\varepsilon$ are not explicit in their work. Their paper relies on doubling space results that bring factors $1/\varepsilon^{O(d)}$ to the exponent of the running time, thus Gap-ETH-tight running times cannot result from their approach. (Nonetheless, we include a more direct overview of their techniques and achieved running times to ours, see Section 1.2.)

In order to obtain tight running times, we need to make a more explicit analysis and not rely on generic doubling space results.

Problem 2.

Is it possible to solve TSP in $\mathbb{H}^{d}$ as fast as in $\mathbb{R}^{d}$ ?

A natural starting point is the recent work on hierarchical decompositions in hyperbolic space and the newly introduced hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen [34]. In fact, García-Castellanos, Medbouhi, Marchetti, Bekkers, and Kragic [26] recently raised the question if a quadtree-based PTAS for hyperbolic Steiner tree is possible. We answer both the question of Problem 2 and of [26] affirmatively.

1.1 Our results

In this paper, we show that explicit Arora-style approximation schemes are possible in hyperbolic space, and we can match the efficiency of Euclidean approximation schemes apart from a factor of $\mathrm{poly}(\log n)$ .

Theorem 1.

For any fixed $d\geq 2$ and any $\varepsilon>0$ , there is a randomized $(1+\varepsilon)$ -approximation for TSP and Steiner tree in $d$ -dimensional hyperbolic space in $2^{O(1/\varepsilon^{d-1})}n(\log n)^{2d(d-1)}$ time.

To make our algorithm work, we need to introduce three new key components compared to earlier work in hyperbolic and Euclidean spaces:

$\blacksquare$

We need to change the hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen [34] into a so-called hybrid hyperbolic quadtree (in short, hybrid tree). We create a hyperbolic shifting technique.
$\blacksquare$

We introduce a new portal placement for the cells of this hybrid tree. The portal placement is non-uniform, in stark contrast with all earlier algorithms.
$\blacksquare$

The proof of our structure theorem is built on a new amortized weighted crossing analysis.

Our techniques readily generalize to the Steiner tree problem and achieve the same running time. This resolves a recent question posed in [26] about hyperbolic Steiner tree. Our result can be considered as an important step toward geometric approximation schemes in non-doubling spaces of negative curvature, and hopefully a first step toward geometric optimization in more general (non-doubling) Riemannian manifolds.

It is important to note that due to our modified shifting technique, there is no polynomial time derandomization for this algorithm for general hyperbolic point sets, again deviating from the Euclidean setting. However, derandomization is possible in case the input has at most constant diameter, and it multiplies the running time by $n^{d}$ in this case. Our derandomization can be stated as follows.

Corollary 2.

For any fixed $d\geq 2$ and any $\varepsilon>0$ , there is a deterministic $(1+\varepsilon)$ -approximation for TSP and Steiner tree in $\mathbb{H}^{d}$ in $2^{O(\mathrm{diam}(P)+1/\varepsilon^{d-1})}n^{d+1}$ $(\log n)^{2d(d-1)}$ time, where $\mathrm{diam}(P)$ is the diameter of the input point set $P\subset\mathbb{H}^{d}$ .

The achieved dependence on $\varepsilon$ is identical to the fastest Euclidean algorithm [31, 40], which is best possible under the so-called Gap Exponential Time Hypothesis (Gap-ETH) [21, 37]. Since a instance in $\mathbb{R}^{d}$ can be scaled to a small neighborhood and embedded in $\mathbb{H}^{d}$ with infinitesimally small distortion, any lower bound in $\mathbb{R}^{d}$ readily applies in $\mathbb{H}^{d}$ .

Corollary 3 (Embedding the lower bound construction of [31]).

For any fixed integer $d\geq 2$ there is a $\gamma>0$ such that there is no $2^{\gamma/\varepsilon^{d-1}}\mathrm{poly}(n)$ time $(1+\varepsilon)$ -approximation algorithm for TSP in $\mathbb{H}^{d}$ under Gap-ETH.

In particular, this means that our running time for TSP is Gap-ETH-tight for any constant $d$ . However, it remains an open problem whether a deterministic running time of $2^{O(1/\varepsilon^{d-1})}n^{O(1)}$ is possible in $\mathbb{H}^{d}$ for point sets of super-constant diameter.

1.2 Overview of our techniques, comparison with earlier work

The techniques of Krauthgamer and Lee [35].

The main idea in the TSP algorithm of Krauthgamer and Lee [35] is to use a randomized embedding of the space into a distribution of trees. This exploits the tree-likeness of hyperbolic spaces at larger scales. At the same time, they propose an Arora-style approach inside balls of radius $\tau$ . Roughly, the space is partitioned into ball-like regions of radius $\tau$ in a randomized fashion, then embedded into a tree whose nodes correspond to partition classes.

The value of $\tau$ and the obtained running times are not explicit in [35]. Here we will briefly speculate about the resulting running time for the sake of comparison. When embedding into a tree with edges of length at least $\tau=\Omega_{\delta}(1/\varepsilon)$ one can observe that the tree distance and the true hyperbolic distance will differ by at most $O(\delta)=O(1)$ , which is at most $(1+O(\varepsilon))\tau$ , i.e., measuring distances between different classes along the tree leads to only $1+O(\varepsilon)$ multiplicative error.

Within the partition classes of diameter $\tau$ , Krauthgamer and Lee must apply doubling space or Arora-style techniques [35]. However, even with newer doubling space algorithms, e.g. [5, 44], the doubling dimension of this neighborhood appears in the second level exponent. Since the doubling dimension of a $\tau$ -radius ball is exponential in $\tau$ , this leads to an at least triple-exponential algorithm in $1/\varepsilon$ . Similarly, using some version of Arora’s algorithm [1] on a distorted Euclidean instance would have to have the solution quality depend on the distortion of the $\tau$ -neighborhood, which is again exponential in $\tau$ . Thus, Arora’s algorithm would have to be invoked with precision at least $\varepsilon^{\prime}=2^{-\tau}$ , leading to a running time that is at least double-exponential in $\tau=\Omega(1/\varepsilon)$ .

Overcoming exponential expansion.

In a more explicit Arora-style algorithm, we have some challenges to overcome, in particular the following.

Ch1: Euclidean quadtrees (and net-trees in doubling spaces) have growth rates that depend only on the dimension, i.e., each cell has $f(d)$ children cells for some fixed function $f$ . This is important as the dynamic program must take into account all portal placements of all children, and in particular, the running time has the number of children in the exponent. Due to the exponential expansion of hyperbolic spaces, no hierarchical decomposition matching the following properties is possible: (a) cells are fat, (b) cells of level $\ell$ have diameter $2^{\Theta(\ell)}$ and (c) each cell is partitioned into $f(d)$ children cells for some fixed function $f$ . This issue was already observed by [34].

This property means that the hyperbolic quadtree of [34] is not suitable for our purposes: the number of children a cell can have is unbounded. Instead, we propose a new structure, called hybrid hyperbolic quadtree, or just hybrid tree for short, that has “open” cells at positive levels, and it fails the diameter property, but keeps fatness, and the number of children for cells is now bounded by $2^{d}$ . At the same time, we can still use the quadtree of [34] for its negative levels; these resemble a slightly distorted $d$ -dimensional Euclidean quadtree, which is only defined now up to cells of diameter $O(1)$ .

Figure 1: (i) The binary tiling of

\mathbb{H}^{2}

with isometric tiles. (ii) The cells of various positive levels of the corresponding quadtree illustrated on the binary tree

T

. (iii) Cells of the new hybrid tree of various positive levels illustrated on

T

.

The binary tiling [13, 14] is a binary tree-like decomposition of the hyperbolic plane into isometric fat tiles. The tiling has a structure that resembles a binary tree: below each tile there are two other tiles, see the illustration in the half-plane model of $\mathbb{H}^{2}$ in Figure 1. For the sake of a simpler description, we compare the quadtree of [34] and our hybrid tree via this binary tree $T$ . In the quadtree of [34], a cell of level $\ell$ will correspond to a subtree of $T$ of height $2^{\ell}$ , which can naturally be cut at half its depth into trees of height $2^{\ell-1}$ , all the way until the tiling at level $0$ is obtained consisting of subtrees of height $1$ (i.e., the vertices of $T$ ). In our hybrid tree, a so-called cell of level $\ell>0$ simply corresponds to a subtree of height $\ell$ . Here we only allow subtrees whose leaves are also leaves of $T$ . The corresponding cell diameter is not exponential in $h$ , but each cell naturally has $2$ children that are cells, plus a single child that is a cell of the binary tiling.

Notice that the resulting cells are “open” from the leaves’ side, i.e., there is no cell below these cells. In particular, we place no portals on the bottom sides of cells of level $\ell\geq 1$ .

Our algorithm.

Handling the hybrid tree in a black box fashion, our algorithm proceeds similarly to Arora’s scheme. We first round our input points to centers of cells of size $\varepsilon\cdot\textsc{opt}/n$ . The level of these cells is $\ell_{\min}$ , and it is useful to think of $\ell_{\min}<0$ for this section.

We apply a random shift on the hybrid tree using the Euclidean vectors in the half-plane model. The shifting is very similar to the Euclidean shifting, with horizontal shifts corresponding to vertical cell boundaries in the bottom layer of the lowest level cells. On the vertical axis, the shifting has only constant range. While the shifting is easy to describe and somewhat natural, it is significantly different from the grid-based shifting in Euclidean space.

The main difficulty, as with all algorithms of this type, is the structure theorem: we need to prove that there exists a $(1+\varepsilon)$ -approximate tour that intersects the cell boundaries only at a few pre-defined portals. In the Euclidean setting, one can prove that the number of intersections between the optimum tour and all grid hyperplanes is $O(\textsc{opt})$ (assuming a minimum edge length of one), and then one can show that the patching cost incurred at each of these intersection points is $O(\varepsilon)$ in expectation. Since hyperbolic spaces are not vector spaces, most of the steps of the analysis fail and need new ideas: we already fail to bound the number of crossings in the same manner, as there is no convenient collection of hyperplanes that could play the role of grid hyperplanes in the Euclidean analysis.

The number of crossings, weighted portal analysis.

In Arora’s algorithm [1], grid lines parallel to each coordinate axis are analyzed in the same uniform manner. However, in a binary tiling, the vertical lines can intersect cells at larger heights and have a non-uniform behaviour. The main challenges with vertical lines (and in higher dimensions, vertical hyperplanes) are as follows:

Ch2: The vertical lines corresponding to our shifts can intersect the optimum tour an unbounded number of times, while in the Euclidean setting, the number of intersections with vertical grid lines is (up to constant factors) equal to the tour length.

We overcome this via weighing the intersection points by the inverse of their $z$ -coordinates. This allows us to have an absolute bound (for every shift) on the number of intersections between the tour and the vertical lines as a function of the length of the optimum tour.
Ch3: In dimension $d\geq 3$ , a side facet of a cell is itself a cell whose structure resembles that of a binary tree. In particular, its surface area is an exponential function of its diameter. This is a very significant problem, as all known algorithms rely on placing portals in a grid-like fashion, ensuring that the distance from a grid point to the nearest portal is at most $\varepsilon$ times the diameter of the facet. In Euclidean space, this requires the placement of $O(1/\varepsilon^{d-1})$ portals inside the hypercube-shaped facet. Here, this would lead to placing a number of portals that is exponential in $1/\varepsilon$ , thus it would lead to a double-exponential running time as a function of $1/\varepsilon$ . Since the number of portals is in the exponent of the running time of Arora-style algorithms, this would lead to a double-exponential dependence on $(1/\varepsilon)$ .

We overcome this challenge via an elaborate portal placement. First, we observe that the probability that an intersection point ends up in a very large cell facet is exponentially small. Thus, we can afford to pay a large patching cost for certain crossings near the bottom of the bounding box with an exponentially small probability. Moreover, we must ensure that the patching cost gets progressively smaller as we get closer to the top of the side facets, as we need to counterbalance the weighted analysis used for the number of crossings. This leads to a non-uniform portal placement. For an illustration of the portal placement on a 2-dimensional $\mathsf{Side}$ facet of a 3-dimensional cell of the hybrid tree, see Figure 2(ii).

Figure 2: Illustration of (i) uniform (naïve) portal placement and (ii) non-uniform portal placement, on a

\mathsf{Side}

facet of a 3-dimensional cell of the hybrid tree. For simplicity, Figure (ii) uses a scaling factor of

2

, although the true scaling factor is

2^{1-1/d}

. The empty circles represent the portals.

The dynamic programming: a banyan for hyperbolic Steiner tree.

The dynamic programming algorithm for hyperbolic TSP can proceed in a bottom-up manner on the hybrid tree, as seen in previous algorithms [1, 31]. In fact, the same structure theorem readily works for the Steiner tree problem, however, there is one difficulty: in the leaf cells (and in compressed cells) of the hybrid tree, the part of the optimum falling there is some Steiner forest, and such a forest can have Steiner points inside these cells. It is non-trivial to find these Steiner points in such a way as to preserve the approximation ratio. In the Euclidean setting, the standard solution is to use a so-called banyan of the portals of the cell.

A $(1+\varepsilon)$ -banyan of the point set $P$ is a geometric graph $G$ on some set $P\cup Q$ such that for any subset $S\subseteq P$ there is a Steiner tree in $G$ for $S$ whose length is at most $1+\varepsilon$ times longer than the optimum Steiner tree of $S$ in the ambient space. In the Euclidean setting of leaf cells, one can take $Q$ to be a dense grid and $G$ to be a complete geometric graph on $P\cup Q$ : this will lead to a solution of size $\mathrm{poly}(1/\varepsilon)$ . However, due to the exponential volume growth in the hyperbolic setting, this is not a viable solution in hyperbolic space at larger distance scales: in this case, we show that it suffices to place potential Steiner points along all edges of a ( $d$ -dimensional) triangulation of portals and input points.

2 Preliminaries

Here we only give concise preliminaries for topics handled in the main text; for further details see the full version [32]. Let $\mathbb{H}^{d}$ and $\mathbb{R}^{d}$ denote $d$ -dimensional hyperbolic space (of sectional curvature $-1$ ) and $d$ -dimensional Euclidean space, respectively, with distance functions $\mathrm{dist}_{\mathbb{H}}$ and $\mathrm{dist}_{\mathbb{R}}$ . For a given set of points $P=\{p_{1},p_{2},\ldots,p_{n}\}$ , a tour is defined to be a cycle $\pi$ that visits each point and returns to its starting point. Let $\mathrm{len}_{\mathbb{R}}(\pi)$ denote its total Euclidean length and $\mathrm{len}_{\mathbb{H}}(\pi)$ its total hyperbolic length. In the hyperbolic Traveling Salesman problem, the goal is to determine the hyperbolic length $\textsc{opt}_{\mathbb{H}}$ of the shortest such tour passing through $P$ . We also let $\textsc{opt}_{\mathbb{R}}$ denote the Euclidean length of an optimal Euclidean tour. A hyperbolic Steiner tree of a point set $P\subseteq\mathbb{H}^{d}$ is a connected geometric graph whose vertex set includes $P$ . The aim of the hyperbolic Steiner Tree problem is to compute a Steiner tree of $P$ with minimum total hyperbolic length. Throughout this paper, we use $\log$ for the base-2 logarithm and $\ln$ for the natural logarithm. For a positive integer $n$ , we use $[n]$ to denote the set $\{1,\dots,n\}$ . For $X\subset\mathbb{H}^{d}$ , we write $\mathrm{diam}(X)$ for the largest hyperbolic distance between any two points of $X$ . For $\delta>0$ , a set $N$ is a $\delta$ -cover of $X$ if every $x\in X$ lies within distance $\delta$ of some $y\in N$ .

Poincaré upper half-space model.

The Poincaré upper half-space model maps hyperbolic space $\mathbb{H}^{d}$ to the Euclidean upper half-space, where each point $p\in\mathbb{H}^{d}$ is represented as $(x(p),z(p))\in\mathbb{R}^{d-1}\times\mathbb{R}_{>0}$ . In this model, the geodesic (shortest path) between $p$ and $q$ is either a vertical Euclidean line segment (when $x(p)=x(q)$ ), or an arc from a Euclidean circle that is perpendicular to the Euclidean hyperplane $z=0$ . The results in this paper are presented in the upper half-space model. We think of the $z$ -direction as going “up” and the $x$ -directions as going “sideways”. For more details, see [14] or the textbooks [6, 29, 45].

Binary tiling.

Let us first define the relevant notation from [34]. In the upper half-space model, an axis-aligned horobox $B$ is a Euclidean axis-aligned box specified by its lexicographically minimal and maximal corner points $(x_{\min}(B),z_{\min}(B))$ and $(x_{\max}(B),z_{\max}(B))$ . A cube-based horobox $B$ is an axis-aligned horobox with $z_{\max}(B)/z_{\min}(B)=2^{h}$ and $(x_{\max}(B)-x_{\min}(B))/z_{\min}(B)=(w,\dots,w)$ , where $w$ is the width of $B$ and $h$ is the height of $B$ .

To define the binary tiling, we begin with the cube-based horobox $C$ such that $x_{\min}(C)=(0,\dots,0)$ and $z_{\min}=1$ , $w(C)=1/\sqrt{d-1}$ and $h(C)=1$ . For $\sigma>0$ and $\tau\in\mathbb{R}^{d-1}$ , let $T_{\sigma,\tau}(x,z)=\sigma\cdot(x+\tau,z)$ be a family of transformations. The binary tiling is obtained by applying transformations $T_{\sigma,\tau}$ , where $\sigma=2^{k}$ for integers $k$ , and $\tau\in\mathbb{Z}^{d-1}$ , to the horobox $C$ . This yields a tiling of $\mathbb{H}^{d}$ into isometric cells that are cube-based horoboxes; see Figure 1(i).

Euclidean tools from [1] and [31].

For small distances, our structure theorem relies on the Euclidean structure theorems of [1] and [31]. For the necessary definitions and the formal statement of these Euclidean structure theorems, we refer the reader to the full version of the paper [32] and to [1, 31].

3 Hybrid Hyperbolic Quadtree and Portals

The hybrid hyperbolic quadtree is a tree whose nodes, called cells, are cube-based horoboxes. Each cell is the disjoint union of its children in the tree and has an integer level such that same-level cells are (almost) isometric. A cell of level $0$ is a cell of the binary tiling. A cell of level $\ell>0$ is the union of its children, which are a cell $C$ from the binary tiling and the $2^{d-1}$ cells of level $\ell-1$ directly below $C$ (for an illustration in $\mathbb{H}^{2}$ , see Figure 1(iii)). Equivalently, a cell $C$ of level $\ell\geq 0$ is a portion of the binary tiling resembling a complete $2^{d-1}$ -ary tree of height $\ell$ , whose subtrees of height $\ell^{\prime}>0$ are exactly the level- $\ell^{\prime}$ descendants of $C$ (see Figure 1(iii)). Note that all the cells of the same positive level are isometric. Cells of levels $\ell<0$ are defined by splitting a binary tiling cell using Euclidean quadtree splits as in the hyperbolic quadtree of [34].

We can also define a compressed hybrid hyperbolic quadtree (shown in Figure 3) analogously to the compressed Euclidean quadtree; the details for this are in [32]. From this point onward, we refer to the hybrid hyperbolic quadtree as the hybrid tree and to the compressed hybrid hyperbolic quadtree as the compressed hybrid tree.

Figure 3: The compressed hybrid tree. (i) A point set and the cells of its compressed hybrid tree (A compressed cell is depicted in dashed lines). (ii) The tree structure of the hybrid tree.

Throughout the paper, the proofs of statements marked with ( $\star$ ) can be found in the full version of the paper [32].

Lemma 4 ( $\star$ ).

Let $P$ be a set of $n$ points in $\mathbb{H}^{d}$ . There exists an $O(2^{d}n+dn\log{n})$ time algorithm to build a compressed hybrid tree on $P$ .

Bounding box.

Let $B$ be the smallest Euclidean axis-aligned bounding box containing $P$ . We first apply the same isometry $T_{\sigma,\tau}$ to both $P$ and $B$ so that $x_{\min}(B)=(0,\dots,0)$ and $z_{\min}(B)=1$ . Let $s$ be the largest of the distances between non-adjacent facets of $B$ .

Lemma 5 ( $\star$ ).

$\mathrm{diam}(B)\leq(d+1)s$ .

Since $B$ is the smallest bounding box, $\textsc{opt}_{\mathbb{H}}\geq s$ . Now, due to Lemma 5, $\textsc{opt}_{\mathbb{H}}\geq(1/(d+1))\cdot\mathrm{diam}(B)$ . Set $\ell_{\min}$ to be the minimum of $0$ and the largest level where twice the diameter of a cell at that level is less than $(\varepsilon/(d+1)n)\cdot\mathrm{diam}(B)$ . Define $\ell_{\max}-1$ as the smallest hybrid tree level at which some cell $C$ fully contains $B$ , then let $B^{*}$ denote the level $\ell_{\max}$ hybrid tree cell whose lexicographically minimal child cell is $C$ .

Perturbation.

Similar to Arora [1], our algorithm perturbs the instance by snapping each point in $P$ to the center of level $\ell_{\min}$ cells (horobox) that contain them. Specifically, each point lying strictly inside a cell is mapped to the center of that cell, while points located on the boundaries of cells are assigned arbitrarily to the center of one of the adjacent cells. After snapping, we introduce an infinitesimal perturbation by adding the offset $\mu\cdot(1,1,\ldots,1)$ to each perturbed point in that cell, for an arbitrarily small $\mu>0$ . This ensures that, under every possible shift of the grid, no perturbed point lies exactly on a cell boundary.

Lemma 6 ( $\star$ ).

The length of an optimal tour over the perturbed points is at most $(1+\varepsilon)\textsc{opt}_{\mathbb{H}}$ .

3.1 Shifting of the hybrid tree

Similarly to Euclidean approximation schemes for TSP, we will use random shifting, though it is worth noting that our “shift” will not be an isometry. Let $\mathcal{C}_{\min}$ denote the cells of level $\ell_{\min}$ that lie in the lexicographically minimal child cell of $B^{*}$ . We pick ${\bf a}_{x}\in\{x_{\min}(C)\mid C\in\mathcal{C}_{\min}\}$ and ${\bf a}_{z}\in\{z_{\min}(C)\mid C\in\mathcal{C}_{\min}\}\cap[1,2)$ uniformly at random, then apply the transformation $(x,z)\mapsto(x-{\bf a}_{x},z/{\bf a}_{z})$ to the hybrid tree. This would be an isometry if ${\bf a}_{z}$ rescaled all coordinates; however, since it only rescales the $z$ -coordinate, the distances are distorted by a factor of at most ${\bf a}_{z}\in[1,2)$ . Consequently, the transformed compressed hybrid tree has slightly different properties from the original hybrid tree, but we can still talk about cells and their children. We denote the shifted compressed hybrid tree under shift ${\bf a}=({\bf a}_{x},{\bf a}_{z})$ by $Q_{\bf a}(P)$ . We stop splitting once cells reach level $\ell_{\min}$ , even if they still contain multiple points.

Lemma 7 ( $\star$ ).

Any level $\ell_{\min}$ cell of $Q_{\bf a}(P)$ contains at most $2^{d-1}$ distinct perturbed points.

Lemma 8 ( $\star$ ).

Let $C$ be a cell of level $0$ in $Q_{\bf a}(P)$ . There is a bijection $\phi:C\to[0,1]^{d}$ such that $\phi(C)$ is a Euclidean unit hypercube that is split in $Q_{\bf a}(P)$ exactly as a Euclidean (compressed) quadtree. Additionally, $\phi$ is bi-Lipschitz: for any $p,q\in C$ ,

\Omega{\left(dist_{\mathbb{H}}(p,q)\right)}\leq\mathrm{dist}_{\mathbb{R}}(\phi% (p),\phi(q))\leq O{\left(\sqrt{d}\cdot\mathrm{dist}_{\mathbb{H}}(p,q)\right)}.

3.2 Portal placement

For any pair of sibling cells in $Q_{\bf a}(P)$ , we now define a set of portals to be placed on their shared boundary. The placement depends on the level $\ell$ of these siblings.

Negative levels.

When $\ell<0$ , we place the portals as in the Euclidean case [31] with a slight modification described below. In the Euclidean setting, the optimal tour consists of $n$ line segments. Each segment crossing between two adjacent (Euclidean) quadtree cells must intersect their common facet. In the hyperbolic setting, however, tour segments can have endpoints in two adjacent negative-level cells but still avoid intersecting their common facet. To address this, we slightly modify the height of the common facet by extending it in the $z$ -direction. This ensures that every geodesic intersects the extended facet; see Figure 4(ii). Correspondingly, for a (hyperbolic or Euclidean) hyperplane $H$ , we say here that a point $q\in H\cap\pi$ is a crossing of the tour $\pi$ , if there exists $i\in[n]$ such that $q$ lies on geodesic $p_{i}p_{i+1}$ and the endpoints $p_{i}$ and $p_{i+1}$ lie on different sides of $H$ ; see Figure 4(i).

Figure 4: (i) The geodesic

s

has a crossing with the hyperplane

H_{1}

, but not with the hyperplane

H_{2}

: although

s

intersects

H_{2}

twice, its endpoints lie on the same side. (ii) Two adjacent negative-level hybrid tree cells

C_{1}

and

C_{2}

share a common facet

F

. Extending

F

upward by a factor of

4

yields

F^{\prime}

, which is intersected by any geodesic

s

joining points

a\in C_{1}

and

b\in C_{2}

.

Lemma 9 ( $\star$ ).

Let $C_{1}$ and $C_{2}$ be two adjacent level- $\ell$ ( $\ell<0$ ) hybrid tree cells sharing a common facet $F$ of Euclidean height $\Delta=2^{2^{\ell}}-1$ . If we extend this facet upward by a factor of $4$ , then every geodesic with endpoints in $C_{1}$ and $C_{2}$ intersects the extended facet $F^{\prime}$ .

Non-negative levels.

We now consider the case $\ell\geq 0$ . Here, even the previously modified Euclidean portal placement cannot be applied directly, as it would result in an exponential blow-up in the number of portals and thus fail to achieve the desired result. To overcome this, we introduce a different portal placement strategy, described below. Note that a boundary facet shared between two sibling cells of level $\ell$ can be of two types:

$\mathsf{Top}$ :: Facets that lie in horizontal Euclidean hyperplanes (hyperbolically these are horospheres). Each such facet is the top boundary of some binary tiling cell.
$\mathsf{Side}$ :: Facets that lie in vertical hyperplanes. These are in fact $(d-1)$ -dimensional cells, so each such facet corresponds to a cell in some $(d-1)$ -dimensional hybrid tree.

Since $\mathsf{Top}$ facets come from binary tiling cells, Lemma 8 means we have constant distortion compared to Euclidean space. Consequently, we can simply construct a $(1/r)$ -cover of the facet by placing a grid of $r^{d-1}\cdot d^{O(d)}$ equally-spaced portals.

For a $\mathsf{Side}$ facet $\sigma$ , recall that $\sigma$ is a cell of some $(d-1)$ -dimensional hybrid tree and can therefore be seen as a complete $2^{d-2}$ -ary tree $T_{\sigma}$ of binary tiling cells. We consider each cell $F$ in $T_{\sigma}$ individually and give a portal placement based on its (hop) distance $h$ to the root of $T_{\sigma}$ . Let $b=2^{1-1/d}$ . If $b^{h}\leq r$ , we place portals according to a $(b^{h}/r)$ -cover in $F$ . Due to Lemma 8, this means we place $d^{O(d)}\cdot(r/b^{h})^{d-1}$ portals. Otherwise, we do not place any portals. Now, the total number of portals placed for a $\mathsf{Side}$ facet is bounded by

\sum_{h=0}^{\infty}2^{h(d-2)}\cdot d^{O(d)}\cdot(r/b^{h})^{d-1}=d^{O(d)}\cdot r% ^{d-1}\sum_{h=0}^{\infty}2^{-h/d}=d^{O(d)}\cdot r^{d-1}.

Observation 10.

For any $\mathsf{Top}$ or $\mathsf{Side}$ facet, we place $r^{d-1}\cdot d^{O(d)}$ portals.

4 Structure Theorem

Now we discuss and prove the structure theorem that allows us to develop a dynamic programming algorithm to solve the Hyperbolic TSP and Steiner Tree problem. We start by adapting the definitions for $r$ -simple geometric graphs and $r$ -simplifications from the Euclidean case [31] to our hyperbolic setting.

Definition 11 ( $r$ -simple geometric graph).

Given a $(d-1)$ -dimensional Euclidean box $F$ , let $F^{*}$ denote $F$ with its $2^{d-1}$ corners removed. A geometric graph $\pi$ is called $r$ -simple if, for each facet $F$ shared by a pair of sibling cells in $Q_{\bf a}(P)$ ,

$\blacksquare$

if $F$ belongs to a non-negative level of the compressed hybrid tree, then the geometric graph $\pi$ crosses $F$ only through the portal points defined in $F$ ; or
$\blacksquare$

if $F$ belongs to a negative level of the compressed hybrid tree, then either $\pi$ crosses $F$ at any number of its corner points and exactly one point of $F^{*}$ , or $\pi$ crosses $F$ only through the points from the uniform grid of size $g$ on $F$ , for some $2^{d-1}\leq g\leq r^{2(d-1)}/{|\pi\cap F^{*}|}$ .

Definition 12 ( $r$ -simplification).

A geometric graph $\pi^{\prime}$ is called an $r$ -simplification of a geometric graph $\pi$ if $\pi^{\prime}$ is $r$ -simple, and in each facet $F$ of a negative level where $|\pi\cap F^{*}|=1$ , the single non-corner crossing of $\pi^{\prime}$ is the point in $\pi\cap F^{*}$ .

Having these definitions, we are now ready to state our main theorem.

Theorem 13 (hyperbolic structure theorem).

Let a be a random shift and let $\pi$ be a tour (or Steiner tree) of the point set $P\subset\mathbb{H}^{d}$ . Then for $r>0$ , there is a tour (resp. Steiner tree) $\pi^{\prime}$ of $P$ that is an $r$ -simplification of $\pi$ such that

\mathbb{E}_{\mathbf{a}}[\mathrm{len}_{\mathbb{H}}(\pi^{\prime})-\mathrm{len}_{% \mathbb{H}}(\pi)]\leq O(d^{3})\cdot\frac{\mathrm{len}_{\mathbb{H}}(\pi)}{r}.

In order to prove Theorem 13, we start by proving a bound on the patching cost of the negative levels of the compressed hybrid tree. Note that we state and prove everything for a tour, but every step works identically for a Steiner tree.

Lemma 14 ( $\star$ ).

Let $\pi_{C}$ be the part of a tour $\pi$ inside a cell $C$ of the binary tiling. Then there exists a tour $\pi^{\prime}_{C}$ in $C$ containing $C\cap P$ and connecting $a,b\in\partial C$ with a path if and only if $a,b\in\partial C$ are connected in $\pi_{C}$ such that $\pi^{\prime}_{C}$ is either

$\blacksquare$

an $r$ -simplification with respect to the negative levels and patched to the portals of [31] or
$\blacksquare$

$r$ -simple with respect to the negative levels and patched to the portals of Arora [1],

and $\pi^{\prime}_{C}$ has expected length $(1+O(d^{3}/r))\mathrm{len}_{\mathbb{H}}(\pi_{C})$ .

Now, we prove our structure theorem.

Proof of Theorem 13..

We describe a patching procedure for negative and non-negative levels of our shifted compressed hybrid tree separately.

Patching negative levels.

We first modify the optimum tour $\pi$ to get a tour $\pi_{1}$ that is slightly longer in expectation, and only crosses the shared boundaries of negative-level sibling cells through portals. In each binary tiling cell $C$ , we apply Lemma 14 on $\pi_{C}=\pi\cap C$ . As a result, we get a collection $\pi^{\prime}_{C}$ of paths in $C$ whose expected length is $(1+O(d^{3}/r))\mathrm{len}_{\mathbb{H}}(\pi\cap C)$ . Let $\pi_{1}$ denote the union of $\pi^{\prime}_{C}$ over all binary tiling cells $C$ . Notice that $\pi_{1}\cap C$ connects two points of $\partial C$ if and only if the same points are connected by $\pi$ , and $\pi_{1}$ covers the same set of input points; thus $\pi_{1}$ is a tour of $P$ of expected length $(1+O(d^{3}/r))\mathrm{len}_{\mathbb{H}}(\pi)$ .

Patching non-negative levels.

We further modify the tour $\pi_{1}$ to get a tour $\pi_{2}$ that is slightly longer in expectation, and only crosses the cell boundaries between non-negative level siblings of the compressed hybrid tree through portals. This can be achieved as follows. For each crossing point $x$ of $\pi_{1}$ with a shared facet $F$ of cell siblings of level at least $0$ , we add two hyperbolic segments on each side of the facet connecting a copy of $x$ and the portal that is closest to $x$ . (Technically, the segments are added at some infinitesimal distance from the facet.) This operation transfers all crossings to the nearest portals. Next, if some portal $v$ is used at least three times by the tour, then by the patching lemma [1, Lemma 3] the tour can be simplified to go through the portal at most twice.

Patching costs on non-negative levels.

To bound the patching cost, we want to give deterministic bounds on the number of intersections between the tour $\pi$ and the hyperplanes used by the cells at level $\ell_{\min}$ , then combine this with the expected cost for each intersection under random shifts ${\bf a}$ . We do this separately for the vertical hyperplanes and the horizontal ones, since their behavior and portal placement differ.

Let $\cal V$ be the set of all vertical hyperplanes obtained by extending the vertical facets of the cells at level $\ell_{\min}$ in the unshifted hybrid tree. Let $\delta$ be the (maximum) diameter of all level $\ell_{\min}$ cells. Since these cells are $\Omega(1/\sqrt{d})$ -fat [34, Theorem 7], we observe the following.

Observation 15.

After perturbation, the distance between two distinct points is $\Omega(\delta/\sqrt{d})$ .

Decompose $\pi$ into consecutive segments $\pi^{1},\dots,\pi^{n}$ . Let $I$ denote the set of intersection points of $\pi$ and all hyperplanes in $\cal V$ . To bound the patching cost of the vertical intersections of the tour $\pi$ , we use a weighted portal analysis. We assign each $q\in I$ a weight equal to $1/z(q)$ . To bound the expected patching cost of the $\mathsf{Side}$ facets, we start by bounding the total weight of intersections in $I$ as follows.

Claim 16.

$\sum_{p\in I}\frac{1}{z(p)}\leq O{\left(\frac{d\sqrt{d}}{\delta}\cdot\mathrm{% len}_{\mathbb{H}}(\pi)\right)}.$

Proof.

We consider each of the $d-1$ horizontal axes separately; let $\cal{V}^{\prime}$ be a set of hyperplanes perpendicular to one of these axes. For each $j\in[n]$ , let $I^{j}=\{p_{1}^{j},\dots,p_{k_{j}}^{j}\}$ be the ordered set of intersection points of $\pi^{j}$ with $\cal V^{\prime}$ , and $I^{\prime}=\bigcup_{j\in[n]}I^{j}$ . For $i\in[k_{j}-1]$ , let $z_{i}^{j}=\min\{z(p_{i}^{j}),z(p_{i+1}^{j})\}$ . The Euclidean distance between adjacent hyperplanes from $\cal{V}^{\prime}$ is given by the horobox width of level- $\ell_{\min}$ cells, which is $w\coloneq\Theta(\delta/\sqrt{d})$ according to [34, Lemma 6]. By [34, Observation 11], the distance from a point $(w,0,\dots,0,z_{i}^{j})$ to hyperplane $x_{1}=0$ is $\mathrm{arsinh}\frac{w}{z_{i}^{j}}$ . Since $\mathrm{arsinh}x=\Omega(x)$ for $x=O(1)$ , $\mathrm{len}_{\mathbb{H}}\big(p_{i}^{j}p_{i+1}^{j}\big)=\Omega{\left(\frac{% \delta}{z_{i}^{j}\sqrt{d}}\right)}$ . Summing this over $i\in[k_{j}-1]$ yields

\displaystyle\mathrm{len}_{\mathbb{H}}(\pi^{j})\geq\sum_{i\in[k_{j}-1]}\mathrm% {len}_{\mathbb{H}}(p_{i}^{j}p_{i+1}^{j})\geq\sum_{i\in[k_{j}-1]}\Omega\left(% \frac{\delta}{z_{i}^{j}\sqrt{d}}\right).

Since $1/(z_{i}^{j})=\max\{1/z(p_{i}^{j}),1/z(p_{i+1}^{j})\}$ , we have $\sum_{i\in[k_{j}-1]}\frac{1}{z_{i}^{j}}\geq\frac{1}{2}\sum_{p\in I^{j}}\frac{1% }{z(p)}$ . Hence, $\sum_{p\in I^{j}}\Omega{\left(\frac{\delta}{\sqrt{d}\cdot z(p)}\right)}$ is a lower bound for $\mathrm{len}_{\mathbb{H}}(\pi^{j})$ . If $k_{j}\leq 1$ (that is $\pi^{j}$ intersects $\mathcal{V}^{\prime}$ at most once), the lower bound follows from Observation 15. Summing over $j\in[n]$ , we have

\mathrm{len}_{\mathbb{H}}(\pi)\geq\sum_{j\in[n]}\sum_{p\in I^{j}}\Omega\left(% \frac{\delta}{\sqrt{d}\cdot z(p)}\right)=\frac{\delta}{\sqrt{d}}\sum_{p\in I^{% \prime}}\Omega\left(\frac{1}{z(p)}\right).

Hence, $\sum_{p\in I^{\prime}}\frac{1}{z(p)}\leq O{\left(\frac{\sqrt{d}}{\delta}\cdot% \mathrm{len}_{\mathbb{H}}(\pi)\right)}$ and summing over all axes gives the claim. $\hfill\vartriangleleft$

Next, we state a bound for the expected patching cost of vertical intersections.

Claim 17.

Let $p\in I$ . Then $\mathbb{E}_{\bf a}[\text{patching cost for }p]=O{\left(\frac{d\cdot\delta}{r% \cdot z(p)}\right)}$ .

Proof.

Figure 5: Distribution of the value

h

used in Claim 17 (here

\ell_{\min}=0

). Note that the solid lines give the binary tiling.

For any vertical hyperplane $V\in\mathcal{V}$ , partition it into regions $(V_{h})_{h\in\mathbb{Z}}$ with the horizontal Euclidean hyperplanes $z=2^{i}/{\bf a}_{z}$ (for all $i\in\mathbb{Z}$ , unrelated to $h$ ) used by the shifted binary tiling. Here, $V_{0}$ denotes the highest region of $V$ that still separates two cells from the shifted binary tiling, and $V_{h+1}$ is the region directly below region $V_{h}$ , as shown in Figure 5. Note that for $h\geq 0$ , any two regions $V_{h}$ and $V^{\prime}_{h}$ (with $V\neq V^{\prime}$ but the same $h$ ) have the same portal placement: if $b^{h}\leq r$ the portals form a $(b^{h}/r)$ -cover and otherwise there are no portals. For the given point $p$ , we now let the random variable $H$ be such that $p\in V_{H}$ for some $V\in\mathcal{V}$ , and calculate the expected patching cost based on the behavior of $H$ .

Note that $H$ depends on the shift $\bf a$ as well as $z(p)$ . Let us first determine the probability distribution of $H$ at the bottom row $z(p)=1/{\bf a}_{z}$ . Note that the number of shifts ${\bf a}_{x}$ giving $H=h$ is twice the number giving $H=h+1$ . Thus, if we have $k$ shifts that give $H=\ell_{\min}$ then $\lfloor k\cdot 2^{\ell_{\min}-h-1}\rfloor$ shifts give $H=h$ . Seeing as we have $2k-1$ shifts in total,

\mathbb{P}(H=h)=O(2^{\ell_{\min}-h})=O(\delta/2^{h}).

For general $z(p)$ , note that $H$ decreases by one every time $z(p)$ doubles and hence

\mathbb{P}(H=h)=O{\left(\delta/2^{h+\log\frac{z(p)}{{\bf a}_{z}}}\right)}=O{% \left(\frac{\delta}{2^{h}z(p)}\right)},

since ${\bf a}_{z}\in[1,2)$ . For convenience, let $t=O(\delta/z(p))$ to simplify this to $\mathbb{P}(H=h)\leq t/2^{h}$ .

When $H\geq 0$ and $b^{H}\leq r$ , the patching cost will be at most $2b^{H}/r$ . If $b^{H}>r$ , we can still route through some other portal on the facet, which will be within distance $O(H-\log_{b}r)$ . If $H<0$ , then the patching cost is zero. Therefore, we have

$\displaystyle\mathbb{E}_{\bf a}[\text{patching cost for }p]$	$\displaystyle\leq\sum_{h=0}^{\log_{b}r}2b^{h}t/(r\cdot 2^{h})+\sum_{h=\log_{b}% r}^{\infty}O(h-\log_{b}r)\cdot t/2^{h}$
	$\displaystyle<\frac{2t}{r}\sum_{h=0}^{\infty}(b/2)^{h}+O(t/2^{\log_{b}r})\sum_% {h=0}^{\infty}h/2^{h}$
	$\displaystyle=\frac{2t}{r}\cdot\frac{1}{1-b/2}+O(t/2^{\log_{b}r})$
	$\displaystyle=\frac{2t}{r}\cdot\frac{1}{1-2^{-1/d}}+O(t/r^{\frac{1}{1-1/d}})$
	$\displaystyle=O(dt/r).$	(since $(1+x)^{r}\leq 1+rx$ for reals $0\leq r\leq 1$ and $x\geq-1$ .)

Hence, the claim follows. $\hfill\vartriangleleft$

Consider the crossings of $\pi_{1}$ with $\mathsf{Side}$ facets. By Claim 16 and Claim 17, we have

\displaystyle\sum_{p\in I}\mathbb{E}_{\mathbf{a}}[\text{patching cost for }p]=% O{\left(\frac{d\delta}{r}\right)}\sum_{p\in I}\frac{1}{z(p)}=O{\left(\frac{d^{% 2}\sqrt{d}}{r}\right)}\mathrm{len}_{\mathbb{H}}(\pi_{1}).

To bound the number of crossings with $\mathsf{Top}$ facets, we have the following claim.

Claim 18 ( $\star$ ).

Let $\Lambda$ be the number of intersections of $\pi$ with $\mathsf{Top}$ facets of non-negative level cells. We have $\mathbb{E}_{\bf a}[\Lambda]=O(\mathrm{len}_{\mathbb{H}}(\pi)\sqrt{d})$ .

For $\mathsf{Top}$ facets, the patching cost is always at most $2/r$ by construction, thus by Claim 18 their expected total patching cost is $O{\left(\frac{\sqrt{d}}{r}\right)}\mathrm{len}_{\mathbb{H}}(\pi_{1})$ . Combining the two contributions, the expected total patching cost is $O{\left(\frac{d^{2}\sqrt{d}}{r}\right)}\mathrm{len}_{\mathbb{H}}(\pi_{1})$ . Finally, using $\mathrm{len}_{\mathbb{H}}(\pi_{1})=(1+O(1/r))\mathrm{len}_{\mathbb{H}}(\pi)$ to express the bound in terms of $\pi$ , we obtain $\mathbb{E}_{\bf a}\big[\mathrm{len}_{\mathbb{H}}(\pi_{2})-\mathrm{len}_{% \mathbb{H}}(\pi_{1})\big]=O{\left(\frac{d^{2}\sqrt{d}}{r}\right)}\mathrm{len}_% {\mathbb{H}}(\pi)$ , as required. We conclude the proof by observing that $\pi^{\prime}\coloneqq\pi_{2}$ is an $r$ -simplification of $\pi$ and has the desired length. $\hfill\blacktriangleleft$

5 Conclusion

In this paper we have obtained approximation schemes for $d$ -dimensional hyperbolic TSP and hyperbolic Steiner tree with running time $2^{O(1/\varepsilon^{d-1})}n\,\mathrm{poly}(\log n)$ (our approximation schemes follow from the structure theorem, mostly using standard techniques; we go into this in the full version [32]). Some interesting open questions remain for future work.

$\blacksquare$

The reason why we do not yet match the running times of [31] is because the faster algorithms rely on light Euclidean spanners, while no light (Steiner) spanners exist for hyperbolic point sets as of yet. Are there Steiner spanners of lightness $\mathrm{poly}(1/\varepsilon)$ in $\mathbb{H}^{d}$ ? What about light banyans?
$\blacksquare$

Is it possible to use the techniques of [40] to get a linear dependence on $n$ ?
$\blacksquare$

Is there a deterministic algorithm for hyperbolic TSP without dependence on the diameter of the input?
$\blacksquare$

It has been observed on several occasions that the complexity of optimization problems in hyperbolic space decreases as points are at larger distance from each other [9, 30, 33]. In line with this, one can embed any hyperbolic point set into an edge-weighted tree with additive error $O(\log n)$ [27, Chapter 6] in time $O(n^{2})$ [19], which already implies an $O(n^{2})$ time TSP algorithm when $\textsc{opt}_{\mathbb{H}}=\Omega(n\log n/\varepsilon)$ . Can we already achieve milder dependence on $\varepsilon$ for smaller $\textsc{opt}_{\mathbb{H}}$ , or keep near-linear dependence on $n$ ?

References

[1] Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753–782, 1998. doi:10.1145/290179.290180.
[2] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the 13th ACM Symposium on the Theory of Computing, (STOC), pages 106–113. ACM, 1998. doi:10.1145/276698.276718.
[3] Yair Bartal and Lee-Ad Gottlieb. A linear time approximation scheme for Euclidean TSP. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science, (FOCS), pages 698–706. IEEE, 2013. doi:10.1109/FOCS.2013.80.
[4] Yair Bartal and Lee-Ad Gottlieb. Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. In Proceedings of the 53rd ACM SIGACT Symposium on Theory of Computing, (STOC), pages 1028–1041. ACM, 2021. doi:10.1145/3406325.3451063.
[5] Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563–1581, 2016. doi:10.1137/130913328.
[6] Riccardo Benedetti and Carlo Petronio. Lectures on Hyperbolic Geometry. Springer Science & Business Media, 1992. doi:10.1007/978-3-642-58158-8.
[7] Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. Network Science, 10(4):361–380, 2022. doi:10.1017/nws.2022.32.
[8] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic random graphs: Separators and treewidth. In Proceedings of the 24th European Symposium on Algorithms, (ESA), volume 57 of LIPIcs, pages 15:1–15:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ESA.2016.15.
[9] Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen. Structure and independence in hyperbolic uniform disk graphs. In Proceedings of the 41st International Symposium on Computational Geometry, (SoCG), volume 332 of LIPIcs, pages 21:1–21:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SOCG.2025.21.
[10] Glencora Borradaile, Philip N. Klein, and Claire Mathieu. A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Trans. Algorithms, 11(3):19:1–19:20, 2015. doi:10.1145/2629654.
[11] Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theor. Comput. Sci., 760:35–54, 2019. doi:10.1016/j.tcs.2018.08.014.
[12] Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D. Ellis Hershkowitz, and Rajmohan Rajaraman. One tree to rule them all: Poly-logarithmic universal steiner tree. In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science, (FOCS), pages 60–76. IEEE, 2023. doi:10.1109/FOCS57990.2023.00012.
[13] 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.
[14] James W Cannon, William J Floyd, Richard Kenyon, Walter R Parry, et al. Hyperbolic geometry. Flavors of geometry, 31(59-115):2, 1997.
[15] T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. ACM Trans. Algorithms, 12(4):55:1–55:22, 2016. doi:10.1145/2915183.
[16] Vincent Cohen-Addad. Approximation schemes for capacitated clustering in doubling metrics. In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2241–2259. SIAM, 2020. doi:10.1137/1.9781611975994.138.
[17] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. J. ACM, 68(6):44:1–44:34, 2021. doi:10.1145/3477541.
[18] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. SIAM Journal on Computing, 48(2):644–667, 2019. Preliminary version in FOCS 2016. doi:10.1137/17M112717X.
[19] Anders Cornect and Eduardo Martínez-Pedroza. Gromov’s approximating tree and the all-pairs bottleneck paths problem. CoRR, 2025. doi:10.48550/arXiv.2408.05338.
[20] Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Streaming algorithms for geometric steiner forest. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 229 of LIPIcs, pages 47:1–47:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.47.
[21] Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloquium Comput. Complex., 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128.
[22] Jittat Fakcharoenphol and Nonthaphat Wongwattanakij. A PTAS for k-hop MST on the euclidean plane: Improving dependency on k. Information Processing Letters, 190:106581, 2025. doi:10.1016/j.ipl.2025.106581.
[23] Arnold Filtser. On strong diameter padded decompositions. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (APPROX/RANDOM), volume 145 of LIPIcs, pages 6:1–6:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.6.
[24] Tobias Friedrich and Anton Krohmer. On the diameter of hyperbolic random graphs. SIAM J. Discret. Math., 32(2):1314–1334, 2018. doi:10.1137/17M1123961.
[25] Octavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Proceedings of the Advances in Neural Information Processing Systems, (NeurIPS), pages 5350–5360, 2018. URL: https://proceedings.neurips.cc/paper/2018/hash/dbab2adc8f9d078009ee3fa810bea142-Abstract.html.
[26] Alejandro García-Castellanos, Aniss Aiman Medbouhi, Giovanni Luca Marchetti, Erik J. Bekkers, and Danica Kragic. HyperSteiner: Computing heuristic hyperbolic Steiner minimal trees. In Proceedings of the 2025 Symposium on Algorithm Engineering and Experiments (ALENEX), pages 194–208. SIAM, 2025. doi:10.1137/1.9781611978339.16.
[27] M. Gromov. Hyperbolic Groups, pages 75–263. Springer, 1987. doi:10.1007/978-1-4613-9586-7_3.
[28] Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Symposium on Foundations of Computer Science, (FOCS), pages 534–543. IEEE, 2003. doi:10.1109/SFCS.2003.1238226.
[29] Birger Iversen. Hyperbolic Geometry, volume 25 of London Mathematical Society Student Texts. Cambridge University Press, 1992. doi:10.1017/CBO9780511569333.
[30] Sándor Kisfaludi-Bak. A quasi-polynomial algorithm for well-spaced hyperbolic TSP. J. Comput. Geom., 12(2):25–54, 2021. doi:10.20382/JOCG.V12I2A3.
[31] Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki. A gap-ETH-tight approximation scheme for Euclidean TSP. J. ACM, 2025. doi:10.1145/3766548.
[32] Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh, and Geert van Wordragen. Gap-ETH-tight algorithms for hyperbolic TSP and Steiner tree. CoRR, 2026. doi:10.48550/arXiv.2603.09834.
[33] Sándor Kisfaludi-Bak and Geert van Wordragen. Near-optimal dynamic Steiner spanners for constant-curvature spaces. CoRR, 2025. doi:10.48550/arXiv.2509.01443.
[34] Sándor Kisfaludi-Bak and Geert van Wordragen. A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space. Journal of Computational Geometry, 16(2):145–174, 2025. doi:10.20382/jocg.v16i2a5.
[35] Robert Krauthgamer and James R. Lee. Algorithms on negatively curved spaces. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, (FOCS), pages 119–132. IEEE, 2006. doi:10.1109/FOCS.2006.9.
[36] An La and Hung Le. Dynamic locality sensitive orderings in doubling metrics. In Proceedings of the 57th ACM Symposium on Theory of Computing, (STOC), pages 1178–1189. ACM, 2025. doi:10.1145/3717823.3718209.
[37] Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 80 of LIPIcs, pages 78:1–78:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.78.
[38] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4):1298–1309, 1999. doi:10.1137/S0097539796309764.
[39] Karim Mnasri, Bhilahari Jeevanesan, and Jörg Schmalian. Critical phenomena in hyperbolic space. Physical Review B, 92:134423, 2015. URL: https://api.semanticscholar.org/CorpusID:118004293.
[40] Tobias Mömke and Hang Zhou. A linear time gap-ETH-tight approximation scheme for Euclidean TSP. CoRR, 2025. arXiv:2411.02585.
[41] Maximilian Nickel and Douwe Kiela. Learning continuous hierarchies in the Lorentz model of hyperbolic geometry. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 3776–3785. PMLR, 2018. URL: http://proceedings.mlr.press/v80/nickel18a.html.
[42] Satish Rao and Warren D. Smith. Approximating geometrical graphs via “spanners” and “banyans”. In Proceedings of the 13th ACM Symposium on the Theory of Computing, (STOC), pages 540–550. ACM, 1998. doi:10.1145/276698.276868.
[43] Yuval Shavitt and Tomer Tankel. On the curvature of the internet and its usage for overlay construction and distance estimation. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM. IEEE, 2004. doi:10.1109/INFCOM.2004.1354510.
[44] Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In Proceedings of the 36th ACM Symposium on Theory of Computing, (STOC), pages 281–290. ACM, 2004. doi:10.1145/1007352.1007399.
[45] William P. Thurston. Three-Dimensional Geometry and Topology, Volume 1. Princeton University Press, 1997. doi:10.1515/9781400865321.
[46] Abraham A. Ungar. Einstein’s special relativity: The hyperbolic geometric viewpoint. CoRR, 2013. arXiv:1302.6961.
[47] Kevin Verbeek and Subhash Suri. Metric embedding, hyperbolic space, and social networks. In Proceedings of the 30th Symposium on Computational Geometry, SoCG, page 501. ACM, 2014. doi:10.1145/2582112.2582139.
[48] Di Wu, Qilong Feng, and Jianxin Wang. Approximation algorithms for fair k-median problem without fairness violation. Theor. Comput. Sci., 985:114332, 2024. doi:10.1016/j.tcs.2023.114332.

[bib.bib1] [1] Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753–782, 1998. doi:10.1145/290179.290180.

[bib.bib2] [2] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the 13th ACM Symposium on the Theory of Computing, (STOC), pages 106–113. ACM, 1998. doi:10.1145/276698.276718.

[bib.bib3] [3] Yair Bartal and Lee-Ad Gottlieb. A linear time approximation scheme for Euclidean TSP. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science, (FOCS), pages 698–706. IEEE, 2013. doi:10.1109/FOCS.2013.80.

[bib.bib4] [4] Yair Bartal and Lee-Ad Gottlieb. Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. In Proceedings of the 53rd ACM SIGACT Symposium on Theory of Computing, (STOC), pages 1028–1041. ACM, 2021. doi:10.1145/3406325.3451063.

[bib.bib5] [5] Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563–1581, 2016. doi:10.1137/130913328.

[bib.bib6] [6] Riccardo Benedetti and Carlo Petronio. Lectures on Hyperbolic Geometry. Springer Science & Business Media, 1992. doi:10.1007/978-3-642-58158-8.

[bib.bib7] [7] Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. Network Science, 10(4):361–380, 2022. doi:10.1017/nws.2022.32.

[bib.bib8] [8] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic random graphs: Separators and treewidth. In Proceedings of the 24th European Symposium on Algorithms, (ESA), volume 57 of LIPIcs, pages 15:1–15:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ESA.2016.15.

[bib.bib9] [9] Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen. Structure and independence in hyperbolic uniform disk graphs. In Proceedings of the 41st International Symposium on Computational Geometry, (SoCG), volume 332 of LIPIcs, pages 21:1–21:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SOCG.2025.21.

[bib.bib10] [10] Glencora Borradaile, Philip N. Klein, and Claire Mathieu. A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Trans. Algorithms, 11(3):19:1–19:20, 2015. doi:10.1145/2629654.

[bib.bib11] [11] Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theor. Comput. Sci., 760:35–54, 2019. doi:10.1016/j.tcs.2018.08.014.

[bib.bib12] [12] Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D. Ellis Hershkowitz, and Rajmohan Rajaraman. One tree to rule them all: Poly-logarithmic universal steiner tree. In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science, (FOCS), pages 60–76. IEEE, 2023. doi:10.1109/FOCS57990.2023.00012.

[bib.bib13] [13] 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.

[bib.bib14] [14] James W Cannon, William J Floyd, Richard Kenyon, Walter R Parry, et al. Hyperbolic geometry. Flavors of geometry, 31(59-115):2, 1997.

[bib.bib15] [15] T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. ACM Trans. Algorithms, 12(4):55:1–55:22, 2016. doi:10.1145/2915183.

[bib.bib16] [16] Vincent Cohen-Addad. Approximation schemes for capacitated clustering in doubling metrics. In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2241–2259. SIAM, 2020. doi:10.1137/1.9781611975994.138.

[bib.bib17] [17] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. J. ACM, 68(6):44:1–44:34, 2021. doi:10.1145/3477541.

[bib.bib18] [18] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. SIAM Journal on Computing, 48(2):644–667, 2019. Preliminary version in FOCS 2016. doi:10.1137/17M112717X.

[bib.bib19] [19] Anders Cornect and Eduardo Martínez-Pedroza. Gromov’s approximating tree and the all-pairs bottleneck paths problem. CoRR, 2025. doi:10.48550/arXiv.2408.05338.

[bib.bib20] [20] Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Streaming algorithms for geometric steiner forest. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 229 of LIPIcs, pages 47:1–47:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.47.

[bib.bib21] [21] Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloquium Comput. Complex., 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128.

[bib.bib22] [22] Jittat Fakcharoenphol and Nonthaphat Wongwattanakij. A PTAS for k-hop MST on the euclidean plane: Improving dependency on k. Information Processing Letters, 190:106581, 2025. doi:10.1016/j.ipl.2025.106581.

[bib.bib23] [23] Arnold Filtser. On strong diameter padded decompositions. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (APPROX/RANDOM), volume 145 of LIPIcs, pages 6:1–6:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.6.

[bib.bib24] [24] Tobias Friedrich and Anton Krohmer. On the diameter of hyperbolic random graphs. SIAM J. Discret. Math., 32(2):1314–1334, 2018. doi:10.1137/17M1123961.

[bib.bib25] [25] Octavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Proceedings of the Advances in Neural Information Processing Systems, (NeurIPS), pages 5350–5360, 2018. URL: https://proceedings.neurips.cc/paper/2018/hash/dbab2adc8f9d078009ee3fa810bea142-Abstract.html.

[bib.bib26] [26] Alejandro García-Castellanos, Aniss Aiman Medbouhi, Giovanni Luca Marchetti, Erik J. Bekkers, and Danica Kragic. HyperSteiner: Computing heuristic hyperbolic Steiner minimal trees. In Proceedings of the 2025 Symposium on Algorithm Engineering and Experiments (ALENEX), pages 194–208. SIAM, 2025. doi:10.1137/1.9781611978339.16.

[bib.bib27] [27] M. Gromov. Hyperbolic Groups, pages 75–263. Springer, 1987. doi:10.1007/978-1-4613-9586-7_3.

[bib.bib28] [28] Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Symposium on Foundations of Computer Science, (FOCS), pages 534–543. IEEE, 2003. doi:10.1109/SFCS.2003.1238226.

[bib.bib29] [29] Birger Iversen. Hyperbolic Geometry, volume 25 of London Mathematical Society Student Texts. Cambridge University Press, 1992. doi:10.1017/CBO9780511569333.

[bib.bib30] [30] Sándor Kisfaludi-Bak. A quasi-polynomial algorithm for well-spaced hyperbolic TSP. J. Comput. Geom., 12(2):25–54, 2021. doi:10.20382/JOCG.V12I2A3.

[bib.bib31] [31] Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki. A gap-ETH-tight approximation scheme for Euclidean TSP. J. ACM, 2025. doi:10.1145/3766548.

[bib.bib32] [32] Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh, and Geert van Wordragen. Gap-ETH-tight algorithms for hyperbolic TSP and Steiner tree. CoRR, 2026. doi:10.48550/arXiv.2603.09834.

[bib.bib33] [33] Sándor Kisfaludi-Bak and Geert van Wordragen. Near-optimal dynamic Steiner spanners for constant-curvature spaces. CoRR, 2025. doi:10.48550/arXiv.2509.01443.

[bib.bib34] [34] Sándor Kisfaludi-Bak and Geert van Wordragen. A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space. Journal of Computational Geometry, 16(2):145–174, 2025. doi:10.20382/jocg.v16i2a5.

[bib.bib35] [35] Robert Krauthgamer and James R. Lee. Algorithms on negatively curved spaces. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, (FOCS), pages 119–132. IEEE, 2006. doi:10.1109/FOCS.2006.9.

[bib.bib36] [36] An La and Hung Le. Dynamic locality sensitive orderings in doubling metrics. In Proceedings of the 57th ACM Symposium on Theory of Computing, (STOC), pages 1178–1189. ACM, 2025. doi:10.1145/3717823.3718209.

[bib.bib37] [37] Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 80 of LIPIcs, pages 78:1–78:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.78.

[bib.bib38] [38] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4):1298–1309, 1999. doi:10.1137/S0097539796309764.

[bib.bib39] [39] Karim Mnasri, Bhilahari Jeevanesan, and Jörg Schmalian. Critical phenomena in hyperbolic space. Physical Review B, 92:134423, 2015. URL: https://api.semanticscholar.org/CorpusID:118004293.

[bib.bib40] [40] Tobias Mömke and Hang Zhou. A linear time gap-ETH-tight approximation scheme for Euclidean TSP. CoRR, 2025. arXiv:2411.02585.

[bib.bib41] [41] Maximilian Nickel and Douwe Kiela. Learning continuous hierarchies in the Lorentz model of hyperbolic geometry. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 3776–3785. PMLR, 2018. URL: http://proceedings.mlr.press/v80/nickel18a.html.

[bib.bib42] [42] Satish Rao and Warren D. Smith. Approximating geometrical graphs via “spanners” and “banyans”. In Proceedings of the 13th ACM Symposium on the Theory of Computing, (STOC), pages 540–550. ACM, 1998. doi:10.1145/276698.276868.

[bib.bib43] [43] Yuval Shavitt and Tomer Tankel. On the curvature of the internet and its usage for overlay construction and distance estimation. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM. IEEE, 2004. doi:10.1109/INFCOM.2004.1354510.

[bib.bib44] [44] Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In Proceedings of the 36th ACM Symposium on Theory of Computing, (STOC), pages 281–290. ACM, 2004. doi:10.1145/1007352.1007399.

[bib.bib45] [45] William P. Thurston. Three-Dimensional Geometry and Topology, Volume 1. Princeton University Press, 1997. doi:10.1515/9781400865321.

[bib.bib46] [46] Abraham A. Ungar. Einstein’s special relativity: The hyperbolic geometric viewpoint. CoRR, 2013. arXiv:1302.6961.

[bib.bib47] [47] Kevin Verbeek and Subhash Suri. Metric embedding, hyperbolic space, and social networks. In Proceedings of the 30th Symposium on Computational Geometry, SoCG, page 501. ACM, 2014. doi:10.1145/2582112.2582139.

[bib.bib48] [48] Di Wu, Qilong Feng, and Jianxin Wang. Approximation algorithms for fair k-median problem without fairness violation. Theor. Comput. Sci., 985:114332, 2024. doi:10.1016/j.tcs.2023.114332.

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Problem 1.

Problem 2.

1.1 Our results

Theorem 1.

Corollary 2.

Corollary 3 (Embedding the lower bound construction of [31]).

1.2 Overview of our techniques, comparison with earlier work

The techniques of Krauthgamer and Lee [35].

Overcoming exponential expansion.

Our algorithm.

The number of crossings, weighted portal analysis.

The dynamic programming: a banyan for hyperbolic Steiner tree.

2 Preliminaries

Poincaré upper half-space model.

Binary tiling.

Euclidean tools from [1] and [31].

3 Hybrid Hyperbolic Quadtree and Portals

Lemma 4 (⋆).

Bounding box.

Lemma 5 (⋆).

Perturbation.

Lemma 6 (⋆).

3.1 Shifting of the hybrid tree

Lemma 7 (⋆).

Lemma 8 (⋆).

3.2 Portal placement

Negative levels.

Lemma 9 (⋆).

Non-negative levels.

Observation 10.

4 Structure Theorem

Definition 11 (r-simple geometric graph).

Definition 12 (r-simplification).

Theorem 13 (hyperbolic structure theorem).

Lemma 14 (⋆).

Proof of Theorem 13..

Patching negative levels.

Patching non-negative levels.

Patching costs on non-negative levels.

Observation 15.

Claim 16.

Proof.

Claim 17.

Proof.

Claim 18 (⋆).

5 Conclusion

References

Lemma 4 ( $\star$ ).

Lemma 5 ( $\star$ ).

Lemma 6 ( $\star$ ).

Lemma 7 ( $\star$ ).

Lemma 8 ( $\star$ ).

Lemma 9 ( $\star$ ).

Definition 11 ( $r$ -simple geometric graph).

Definition 12 ( $r$ -simplification).

Lemma 14 ( $\star$ ).

Claim 18 ( $\star$ ).