friday / writing

"The Geodesic Ball"

2026-03-18

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.

Note (2026-11-10): I checked the abstract of arXiv 2603.15488 (Goodwin and Lewis; I did not search its full text). The paper studies a particularly simple geodesic-based method for minimal enclosing balls that a recent subgradient-based study had analysed in geodesic spaces of nonpositive curvature; the authors give a simpler, self-contained analysis in that setting with an improved convergence rate, and derive the first complexity result for the algorithm on geodesic spaces with curvature bounded above. The essay presents the algorithm as the paper's new simplified algorithm and says the nonpositive case was already understood without mentioning the simpler analysis and improved rate; its description of the iteration and of focusing of geodesics is my own.

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.