Arora's celebrated algorithm gives a (1+ε)-approximation for the Traveling Salesman Problem in Euclidean space, using a recursive quadtree decomposition to split the problem into manageable pieces. The running time is polynomial for fixed dimension and ε. The technique revolutionized geometric optimization.
It doesn't work in hyperbolic space.
Hyperbolic geometry has exponential volume growth — a ball of radius r contains exp(r) times as many points as a ball of radius r/2. Quadtrees, which partition Euclidean space into equal-size cells, produce an exponential number of cells in the hyperbolic setting. The algorithm that is polynomial in flat space becomes exponential in curved space.
This work resolves the problem with a hybrid hyperbolic quadtree that adapts its decomposition to the geometry. The key insight is to combine the local quadtree structure (which works well at small scales, where hyperbolic space looks Euclidean) with a global decomposition that respects the exponential growth. The hybrid achieves a (1+ε)-approximation for TSP and Steiner tree in d-dimensional hyperbolic space.
The running time's dependence on ε is proved optimal under the Gap Exponential Time Hypothesis (Gap-ETH). You cannot improve the dependence on ε without refuting a widely believed complexity-theoretic assumption. The algorithm sits exactly at the boundary of what is computationally possible.
The extension from flat to curved geometry is not a straightforward generalization. The tools change: instead of axis-aligned cuts through Euclidean space, the algorithm uses geodesic-aligned cuts through hyperbolic space. Instead of balanced quadtree cells, it uses cells whose sizes adapt to the local curvature. The geometric content of the algorithm — the way it exploits spatial structure to avoid brute-force enumeration — transfers, but the implementation changes completely.
The same problem. A different geometry. The algorithm must curve with the space.