The traveling salesman problem in flat Euclidean space has a long history of approximation schemes, but extending these to curved geometries introduces complications that are not merely technical but structural. Kisfaludi-Bak, Odak, Singh, and van Wordragen have produced a (1+epsilon)-approximation algorithm for TSP in d-dimensional hyperbolic space with running time 2^{O(1/epsilon^{d-1})} * n^{1+o(1)}, and they show this dependence on epsilon is tight under the Gap Exponential Time Hypothesis. They achieve corresponding results for the hyperbolic Steiner tree problem.
The central architectural insight is a “hybrid hyperbolic quadtree” -- a spatial decomposition that does not simply transplant Arora's Euclidean dissection into negative curvature. Hyperbolic space expands exponentially with radius, so uniform grid decompositions waste enormous resources on distant, sparsely populated regions while underserving dense local clusters. The hybrid quadtree accommodates this by switching between Euclidean-style subdivision in compact neighborhoods and hyperbolic-native partitioning at scale. The portal placement strategy is non-uniform, weighted by local geometric density rather than spread evenly along cell boundaries. What makes this tight is that the lower bound comes from the same curvature: the exponential volume growth that complicates the algorithm also limits how much any alternative approach can compress the search.
Note (2026-11-11): checked against the paper's full text (this essay had been logged as held up on an abstract-level read). The authors, the running time, the hybrid hyperbolic quadtree, the non-uniform portal placement and the Steiner tree extension are as in the paper. Three statements go beyond it. (1) The essay says the tightness comes from the curvature: that the lower bound comes from the same exponential volume growth that complicates the algorithm. In the paper the lower bound is the Euclidean one. Its Corollary 3 observes that an instance in Euclidean space can be scaled to a small neighbourhood and embedded in hyperbolic space with infinitesimally small distortion, so any Euclidean lower bound under Gap-ETH carries over; the algorithm's dependence on epsilon is identical to the fastest Euclidean algorithm. (2) The essay describes the hybrid quadtree as switching between Euclidean-style subdivision in compact neighbourhoods and hyperbolic-native partitioning at scale. The paper describes a tree whose cells are cube-based horoboxes, with open cells at positive levels, that keeps fatness and bounds the number of children of a cell, and that fails the diameter property; I did not find the essay's switching description. (3) The paper states that it remains open whether a deterministic running time of the same form is possible in hyperbolic space for point sets of super-constant diameter, which the essay does not mention; the algorithm is randomized.
This suggests that optimization on curved manifolds is not simply harder than on flat space but differently structured -- the geometry that inflates the problem also provides the leverage for decomposition. The result opens a question about other metric spaces with non-trivial curvature: whether each geometry admits its own natural decomposition hierarchy, and whether tightness results will generally follow from the same geometric property that makes the problem hard.
(arXiv:2603.09834)