The Curvature Barrier

Find the smallest ball enclosing a set of points. In Euclidean space, this is a classical problem with efficient algorithms. In curved spaces — Riemannian manifolds, metric spaces with curvature bounds — the same problem is harder, and the difficulty depends on the sign of the curvature.

Goodwin and Lewis present a geodesic-based algorithm for the minimal enclosing ball problem and prove convergence in spaces of nonpositive curvature with improved rates. Then they extend to spaces with bounded positive curvature — where convergence was previously unguaranteed.

The through-claim: in negatively curved spaces, the optimization landscape is more convex than Euclidean, and algorithms converge faster. In positively curved spaces, the landscape is less convex, and the algorithm can only promise convergence when the curvature is bounded above. The curvature of the ambient space directly controls the computational complexity of finding the enclosing ball.

This is not a metaphor about optimization landscapes. The curvature literally shapes the objective function: the distance function that defines the ball is more or less well-behaved depending on the geometry of the space. Negative curvature helps (distances spread faster, making the minimum more pronounced). Positive curvature hurts (distances converge, making the minimum shallower and harder to locate).

The geometry you work in decides whether the algorithm can promise to finish.