Minimal enclosing balls via geodesics

Adrian S. Lewis; Ariel Goodwin

arxiv: 2603.15488 · v2 · submitted 2026-03-16 · 🧮 math.OC · cs.CG

Minimal enclosing balls via geodesics

Ariel Goodwin , Adrian S. Lewis This is my paper

Pith reviewed 2026-05-15 10:06 UTC · model grok-4.3

classification 🧮 math.OC cs.CG

keywords minimal enclosing ballgeodesic subgradientcomplexity analysisnonpositive curvaturecurvature bounded abovegeodesic metric spacesconvex optimization

0 comments

The pith

A geodesic subgradient method for minimal enclosing balls admits a simpler analysis that improves convergence rates in nonpositive curvature spaces and gives the first known rates when curvature is bounded above.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a simpler and self-contained complexity analysis for a basic geodesic subgradient iteration used to solve minimal enclosing ball problems. It improves the previously known convergence rate in geodesic spaces of nonpositive curvature. It also supplies the first complexity bound for the same iteration when the underlying space has curvature bounded above by some constant. Readers would care because these guarantees make the method more practical for optimization tasks that naturally live in curved metric spaces such as hyperbolic geometry or certain manifolds.

Core claim

The geodesic subgradient iteration for the minimal enclosing ball problem admits a simpler, intuitive, self-contained complexity analysis in geodesic spaces of nonpositive curvature that improves the convergence rate, and the same analysis yields the first complexity result for the iteration on geodesic spaces whose curvature is bounded above.

What carries the argument

The geodesic subgradient iteration, a method that repeatedly steps along geodesics in the direction of a subgradient of the radius function to locate the smallest enclosing ball.

If this is right

The algorithm converges at a strictly better rate than previously established when curvature is nonpositive.
Complexity guarantees now exist for the iteration on the larger class of spaces with curvature bounded above.
The proof requires no external results and can be followed directly from the metric properties.
The same iteration becomes a viable candidate for use on a wider collection of curved spaces.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The simplified proof technique may apply to other subgradient-style methods that move along geodesics.
Implementations on Riemannian manifolds with controlled sectional curvature could inherit these rates after discretization.
The bounds suggest testing the iteration on data sets whose natural geometry is hyperbolic or spherical.

Load-bearing premise

The space must be a geodesic metric space whose curvature is either nonpositive or bounded above by a fixed constant.

What would settle it

A concrete computation or simulation in a geodesic space with curvature bounded above in which the observed convergence rate of the iteration is slower than the derived bound would falsify the claim.

Figures

Figures reproduced from arXiv: 2603.15488 by Adrian S. Lewis, Ariel Goodwin.

read the original abstract

Algorithms for minimal enclosing ball problems are often geometric in nature. To highlight the metric ingredients underlying their efficiency, we focus here on a particularly simple geodesic-based method. A recent subgradient-based study proved a complexity result for this method in the broad setting of geodesic spaces of nonpositive curvature. We present a simpler, intuitive and self-contained complexity analysis in that setting, which also improves the convergence rate. We furthermore derive the first complexity result for the algorithm on geodesic spaces with curvature bounded above.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Cleaner self-contained proof improves the rate for geodesic subgradient minimal enclosing balls in CAT(0) spaces and gives the first explicit bound when curvature is bounded above.

read the letter

The main takeaway is that this paper supplies a simpler, intuitive complexity analysis for the geodesic subgradient iteration on minimal enclosing balls. It tightens the rate in nonpositive curvature spaces relative to the prior subgradient work and supplies the first such bound for spaces whose curvature is bounded above by a fixed constant. The derivation relies on standard comparison-triangle arguments and stays self-contained, which is a clear improvement in readability. The claims line up with the stated assumptions on geodesic metric spaces and the specific iteration, with no visible circularity or dependence on fitted constants. The extension to bounded-above curvature is new relative to the literature referenced in the abstract. Soft spots are minor. The analysis treats the curvature bound as known, which is reasonable for the theoretical setting but could limit immediate applicability where that constant must be estimated from data. Without the full proofs in front of me I cannot exclude small technical gaps in the rate derivations, yet the stress-test note and internal consistency of the abstract give no reason to expect load-bearing problems. The citation pattern is focused and appropriate. This paper is aimed at researchers working on geometric optimization and manifold algorithms who want explicit rates rather than purely asymptotic statements. A reader already familiar with CAT(κ) geometry will extract the most value from the cleaner proof and the new bound. It deserves a serious referee because the novelty is concrete and the argument appears grounded on its own terms. I would send it out for peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript analyzes a simple geodesic subgradient iteration for the minimal enclosing ball problem. It supplies a self-contained, intuitive complexity proof for geodesic spaces of nonpositive curvature (CAT(0)) that improves the previously established rate, and it derives the first complexity bound for the same iteration when the underlying geodesic space has curvature bounded above by a constant.

Significance. If the derivations hold, the work strengthens the metric-geometric toolkit for nonsmooth optimization by replacing a prior subgradient argument with a direct comparison-triangle analysis that yields a strictly better rate in CAT(0) spaces and supplies the first explicit bound in the CAT(κ) setting. These results are directly usable for convergence guarantees on manifolds and other non-Euclidean domains.

major comments (2)

[§3.2] §3.2, the improved CAT(0) rate: the new bound is stated to be strictly better than the cited subgradient result, yet the manuscript does not display the two rates side-by-side or isolate the precise improvement (e.g., the factor by which the leading constant is reduced).
[§4] §4, Theorem 4.1 (curvature-bounded-above case): the complexity expression contains an unspecified dependence on the upper curvature bound κ; without an explicit functional form or a uniform bound independent of κ, the result cannot be compared quantitatively with the CAT(0) case.

minor comments (2)

[§4] Notation for the curvature constant κ is introduced only in §4; an earlier global definition would improve readability.
[Figure 1] Figure 1 caption does not state the dimension or the specific CAT(κ) value used in the numerical example.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation of minor revision. We address the two major comments point by point below and have incorporated the suggested clarifications into the revised manuscript.

read point-by-point responses

Referee: [§3.2] §3.2, the improved CAT(0) rate: the new bound is stated to be strictly better than the cited subgradient result, yet the manuscript does not display the two rates side-by-side or isolate the precise improvement (e.g., the factor by which the leading constant is reduced).

Authors: We agree that an explicit side-by-side comparison would make the improvement more transparent. In the revised manuscript we have added a short remark in §3.2 that quotes the earlier subgradient bound and places it next to the new comparison-triangle bound, thereby isolating the reduction in the leading constant while preserving the same O(1/n) dependence. revision: yes
Referee: [§4] §4, Theorem 4.1 (curvature-bounded-above case): the complexity expression contains an unspecified dependence on the upper curvature bound κ; without an explicit functional form or a uniform bound independent of κ, the result cannot be compared quantitatively with the CAT(0) case.

Authors: The dependence on κ enters the proof of Theorem 4.1 through the geometry of the comparison triangles in the CAT(κ) space. We have revised the statement of the theorem to display this dependence explicitly in terms of the diameter of the set and the curvature bound κ. A uniform bound independent of κ cannot be expected in general, since the geometry changes with κ, but the explicit form now allows direct quantitative comparison with the CAT(0) case recovered as κ → 0. revision: yes

Circularity Check

0 steps flagged

No significant circularity; self-contained re-derivation

full rationale

The paper re-derives the subgradient iteration complexity for minimal enclosing balls in CAT(0) spaces using standard comparison-triangle arguments, improving the rate, and extends the result to CAT(κ) spaces with κ bounded above. The analysis is presented as independent of the cited prior subgradient proof; no equations reduce the claimed rates to fitted constants, self-defined quantities, or load-bearing self-citations. The central claims rest on geometric properties of geodesic spaces rather than renaming or smuggling ansatzes from the authors' own prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard comparison-geometry axioms for geodesic spaces with curvature bounds; no new entities or fitted parameters are introduced.

axioms (1)

domain assumption The ambient space is a geodesic metric space whose sectional curvature is either nonpositive or bounded above by a fixed constant.
Invoked throughout the complexity analysis; standard in the cited comparison-geometry literature.

pith-pipeline@v0.9.0 · 5360 in / 1152 out tokens · 39552 ms · 2026-05-15T10:06:00.021345+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1... min F(x_k)-min F ≤ 4D²/(N+1) ... using inequality (1) d²(αx+βy,z)≤αd²(x,z)+βd²(y,z)-αβd²(x,y)
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Assumption B... complete CAT(κ) space, diameter < π/(2√κ) if κ>0

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Altschuler, S

J.M. Altschuler, S. Chewi, P. Gerber, and A.J. Stromme. Averaging on the Bures- Wasserstein manifold: dimension-free convergence of gradient descent. InNeurIPS Proceedings, 2021

work page 2021
[2]

Ardila, M

F. Ardila, M. Owen, and S. Sullivant. Geodesics in CAT(0) cubical complexes.Ad- vances in Applied Mathematics, 48(1):142–163, 2012

work page 2012
[3]

Arnaudon and F

M. Arnaudon and F. Nielsen. On approximating the Riemannian 1-center.Compu- tational Geometry, 46(1):93–104, 2013

work page 2013
[4]

Bˆ adoiu and K

M. Bˆ adoiu and K. L. Clarkson. Smaller core-sets for balls. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, pages 801–802, USA, 2003. Society for Industrial and Applied Mathematics

work page 2003
[5]

Baˇ c´ ak.Convex Analysis and Optimization in Hadamard Spaces

M. Baˇ c´ ak.Convex Analysis and Optimization in Hadamard Spaces. De Gruyter, 2014

work page 2014
[6]

Beck.First-Order Methods in Optimization

A. Beck.First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017

work page 2017
[7]

L. J. Billera, S. P. Holmes, and K. Vogtmann. Geometry of the space of phylogenetic trees.Advances in Applied Mathematics, 27(4):733–767, 2001

work page 2001
[8]

Boumal.An Introduction to Optimization on Smooth Manifolds

N. Boumal.An Introduction to Optimization on Smooth Manifolds. Cambridge Uni- versity Press, 2023

work page 2023
[9]

M. R. Bridson and A. Haefliger.Metric Spaces of Non-Positive Curvature. Grundlehren der mathematischen Wissenschaften. Springer Berlin, Heidelberg, 1st edition, 1999

work page 1999
[10]

Criscitiello and J

C. Criscitiello and J. Kim. Horospherically convex optimization on Hadamard man- ifolds part I: Analysis and algorithms, 2025. arXiv:2505.16970

work page arXiv 2025
[11]

G. Y. Handler. Minimax location of a facility in an undirected tree graph.Trans- portation Science, 7(3):287–293, 1973. 8

work page 1973
[12]

K. Hayashi. A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes.Discrete & Computational Geometry, 65(3):636–654, 2021

work page 2021
[13]

A. S. Lewis, G. Lopez-Acedo, and A. Nicolae. Horoballs and the subgradient method,

work page
[14]

Massart, J

E. Massart, J. M. Hendrickx, and P.-A. Absil. Curvature of the manifold of fixed-rank positive-semidefinite matrices endowed with the Bures–Wasserstein metric. InGe- ometric Science of Information, pages 739–748, Cham, 2019. Springer International Publishing

work page 2019
[15]

Nock and F

R. Nock and F. Nielsen. Fitting the smallest enclosing Bregman ball. InEuropean Conference on Machine Learning (ECML), pages 649–656, 2005

work page 2005
[16]

Ohta and M

S. Ohta and M. P´ alfia. Discrete-time gradient flows and law of large numbers in Alexandrov spaces.Calculus of Variations and Partial Differential Equations, 54(2):1591–1610, 2015

work page 2015
[17]

Owen and J

M. Owen and J. S. Provan. A fast algorithm for computing geodesic distances in tree space.IEEE/ACM Trans. Comput. Biol. Bioinformatics, 8(1):2–13, January 2011

work page 2011
[18]

J. J. Sylvester. A question in the geometry of situation.Quarterly Journal of Math- ematics, 1:79, 1857

work page
[19]

A. Takatsu. Wasserstein geometry of Gaussian measures.Osaka Journal of Mathe- matics, 48(4):1005–1026, 2011

work page 2011
[20]

Y. Wang, Y. Li, Q. Yang, and H. Ding. Finding Wasserstein ball center: Efficient algorithm and the applications in fairness. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofProceedings of Machine Learning Research, pages 63490–63515. PMLR, 13–19 Jul 2025. 9

work page 2025

[1] [1]

Altschuler, S

J.M. Altschuler, S. Chewi, P. Gerber, and A.J. Stromme. Averaging on the Bures- Wasserstein manifold: dimension-free convergence of gradient descent. InNeurIPS Proceedings, 2021

work page 2021

[2] [2]

Ardila, M

F. Ardila, M. Owen, and S. Sullivant. Geodesics in CAT(0) cubical complexes.Ad- vances in Applied Mathematics, 48(1):142–163, 2012

work page 2012

[3] [3]

Arnaudon and F

M. Arnaudon and F. Nielsen. On approximating the Riemannian 1-center.Compu- tational Geometry, 46(1):93–104, 2013

work page 2013

[4] [4]

Bˆ adoiu and K

M. Bˆ adoiu and K. L. Clarkson. Smaller core-sets for balls. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, pages 801–802, USA, 2003. Society for Industrial and Applied Mathematics

work page 2003

[5] [5]

Baˇ c´ ak.Convex Analysis and Optimization in Hadamard Spaces

M. Baˇ c´ ak.Convex Analysis and Optimization in Hadamard Spaces. De Gruyter, 2014

work page 2014

[6] [6]

Beck.First-Order Methods in Optimization

A. Beck.First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017

work page 2017

[7] [7]

L. J. Billera, S. P. Holmes, and K. Vogtmann. Geometry of the space of phylogenetic trees.Advances in Applied Mathematics, 27(4):733–767, 2001

work page 2001

[8] [8]

Boumal.An Introduction to Optimization on Smooth Manifolds

N. Boumal.An Introduction to Optimization on Smooth Manifolds. Cambridge Uni- versity Press, 2023

work page 2023

[9] [9]

M. R. Bridson and A. Haefliger.Metric Spaces of Non-Positive Curvature. Grundlehren der mathematischen Wissenschaften. Springer Berlin, Heidelberg, 1st edition, 1999

work page 1999

[10] [10]

Criscitiello and J

C. Criscitiello and J. Kim. Horospherically convex optimization on Hadamard man- ifolds part I: Analysis and algorithms, 2025. arXiv:2505.16970

work page arXiv 2025

[11] [11]

G. Y. Handler. Minimax location of a facility in an undirected tree graph.Trans- portation Science, 7(3):287–293, 1973. 8

work page 1973

[12] [12]

K. Hayashi. A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes.Discrete & Computational Geometry, 65(3):636–654, 2021

work page 2021

[13] [13]

A. S. Lewis, G. Lopez-Acedo, and A. Nicolae. Horoballs and the subgradient method,

work page

[14] [14]

Massart, J

E. Massart, J. M. Hendrickx, and P.-A. Absil. Curvature of the manifold of fixed-rank positive-semidefinite matrices endowed with the Bures–Wasserstein metric. InGe- ometric Science of Information, pages 739–748, Cham, 2019. Springer International Publishing

work page 2019

[15] [15]

Nock and F

R. Nock and F. Nielsen. Fitting the smallest enclosing Bregman ball. InEuropean Conference on Machine Learning (ECML), pages 649–656, 2005

work page 2005

[16] [16]

Ohta and M

S. Ohta and M. P´ alfia. Discrete-time gradient flows and law of large numbers in Alexandrov spaces.Calculus of Variations and Partial Differential Equations, 54(2):1591–1610, 2015

work page 2015

[17] [17]

Owen and J

M. Owen and J. S. Provan. A fast algorithm for computing geodesic distances in tree space.IEEE/ACM Trans. Comput. Biol. Bioinformatics, 8(1):2–13, January 2011

work page 2011

[18] [18]

J. J. Sylvester. A question in the geometry of situation.Quarterly Journal of Math- ematics, 1:79, 1857

work page

[19] [19]

A. Takatsu. Wasserstein geometry of Gaussian measures.Osaka Journal of Mathe- matics, 48(4):1005–1026, 2011

work page 2011

[20] [20]

Y. Wang, Y. Li, Q. Yang, and H. Ding. Finding Wasserstein ball center: Efficient algorithm and the applications in fairness. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofProceedings of Machine Learning Research, pages 63490–63515. PMLR, 13–19 Jul 2025. 9

work page 2025