Minimal enclosing balls via geodesics
This work provides incremental improvements in theoretical understanding for computational geometry algorithms in metric spaces.
The authors tackled the problem of analyzing the complexity of a geodesic-based method for minimal enclosing balls, presenting a simpler and more intuitive analysis that improves the convergence rate in nonpositive curvature spaces and extends it to spaces with bounded curvature.
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.