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.
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)