21829 articles – 15616 Notices  [english version]

hal-00560187, version 1

On Approximating the Riemannian 1-Center

Marc Arnaudon () 1, Frank Nielsen () 2, 3

(24/01/2011)

Résumé : In this paper, we generalize the simple Euclidean 1-center approximation algorithm of Badoiu and Clarkson (2003) to Riemannian geometries and study accordingly the convergence rate. We then show how to instantiate this generic algorithm to two particular cases: (1) hyperbolic geometry, and (2) Riemannian manifold of symmetric positive definite matrices.

  • 1 :  Laboratoire de Mathématiques et Applications (LMA-Poitiers)
  • CNRS : UMR6086 – Université de Poitiers
  • 2 :  Laboratoire d'informatique de l'école polytechnique (LIX)
  • CNRS : UMR7161 – Polytechnique - X
  • 3 :  Sony Computer Science Laboratories
  • Sony
  • Domaine : Informatique/Géométrie algorithmique
    Mathématiques/Géométrie différentielle
  • Mots-clés : 1-center – minimax – circumcenter – Riemannian geometry – core-set – approximation
  • Versions disponibles :  v1 (27-01-2011) v2 (22-02-2012)
 
  • hal-00560187, version 1
  • http://hal.archives-ouvertes.fr/hal-00560187
  • oai:hal.archives-ouvertes.fr:hal-00560187
  • Contributeur : Marc Arnaudon <>
  • Soumis le : Jeudi 27 Janvier 2011, 15:38:46
  • Dernière modification le : Jeudi 27 Janvier 2011, 16:43:43