On approximating the Riemannian 1-center (Q714906)

Computing the smallest enclosing ball (SEB) of a finite Euclidean point set is a fundamental problem that was first posed by Sylvester [``A question in the geometry of situation'', Q. J. Math. 1, 79 (1857)]. This problem has been thoroughly investigated in the computational geometry by many mathematicians, where it is known as the minimum enclosing ball, the I-center problem. Since computing the smallest ball exactly is intractable in high dimensions, efficient approximation algorithms have been proposed by \textit{M. Bădoiu} and \textit{K. L. Clarkson} [Comput. Geom. 40, No. 1, 14--22 (2008; Zbl 1138.68056)] and proved the existence of core set \(C \subset P\) o optimal size \(|C| = [1/\epsilon]\) so that \(r(C) \leq (1 +\epsilon) r(P)\) (for any arbitrary \(\epsilon> 0\)) where \(r(S)\) denotes the radius of the SEB of \(S\). In this paper, the authors extend the Euclidean I-center approximation algorithm of Bădoiu and Clarkson [loc. cit.] to arbitrary Riemannian geometries and investigate the corresponding convergence rate. It is also shown that how to instantiate this generic algorithm to two particular settings of the hyperbolic manifold and the manifold of symmetric positive definite matrices.