Approximating Covering and Minimum Enclosing Balls in Hyperbolic Geometry  Frank Nielsen, Gaëtan Hadjeres

Authors : Frank Nielsen, Gaëtan Hadjeres
DOI URL : http://dx.doi.org/10.1007/9783319250403_63
Video : http://www.youtube.com/watch?v=lyCUSd_dYC4
Slides: Nielsen_Approximating covering Minimum balls.pdf
Presentation : https://www.see.asso.fr/node/14264
Creative Commons AttributionShareAlike 4.0 InternationalAbstract:
We generalize the O(dnϵ2)time (1 + ε)approximation algorithm for the smallest enclosing Euclidean ball [2,10] to point sets in hyperbolic geometry of arbitrary dimension. We guarantee a O(1/ϵ2) convergence time by using a closedform formula to compute the geodesic αmidpoint between any two points. Those results allow us to apply the hyperbolic kcenter clustering for statistical locationscale families or for multivariate spherical normal distributions by using their Fisher information matrix as the underlying Riemannian hyperbolic metric.