On approximating the Riemannian 1-center (Q714906)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On approximating the Riemannian 1-center |
scientific article |
Statements
On approximating the Riemannian 1-center (English)
0 references
12 October 2012
0 references
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.
0 references
1-center
0 references
minimax center
0 references
Riemannian geometry
0 references
core-set
0 references
smallest enclosing ball
0 references
finite Euclidean point set
0 references
computational geometry
0 references
algorithm
0 references