The minimal enclosing ball problem — find the smallest ball containing a set of points — is classical in Euclidean space, solvable in linear expected time by Welzl's algorithm. In Riemannian manifolds, the problem becomes harder because balls are defined by geodesic distance and the curvature of the space affects how balls grow.
Goodwin and Lewis (arXiv:2603.15488) provide a simplified geodesic-based algorithm for minimal enclosing balls that achieves the first convergence guarantee for spaces with curvature bounded above — not just nonpositively curved spaces (like Hadamard manifolds) where the problem was already understood.
The challenge in positively curved spaces is that geodesics can focus. Two points that are far apart in geodesic distance might be close in terms of the angles subtended from the center. This focusing means that the ball's center can be sensitive to point placement in ways that don't arise in flat or negatively curved geometry. The algorithm must navigate this sensitivity.
The solution uses geodesics directly rather than embedding the manifold in a higher-dimensional Euclidean space. Each iteration moves the candidate center along the geodesic toward the farthest point, with a step size controlled by the curvature bound. The curvature bound guarantees that this greedy strategy converges — the farthest point gets closer at each step, and the process terminates.
The convergence proof for the bounded-above case was the gap. For nonpositive curvature, geodesic convexity makes the argument straightforward. For positive curvature, the argument requires quantitative control over how geodesic distances change when the center moves — essentially, a stability estimate for the distance function in curved space. The curvature bound provides exactly this control.