Kinetic Maintenance of Mobile k-Centre in Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Kinetic Maintenance of Mobile k-Centre in Trees

Stéphane Durocher
  • Fonction : Auteur
  • PersonId : 836943
Christophe Paul

Résumé

Let C denote a set of n mobile clients, each of which follows a continuous trajectory on a weighted tree T. We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of C. When each client in C moves with linear motion along a path on T we derive a tight bound of \Theta(n) on the complexity of the motion of the 1-centre and corresponding bounds of O(n^2 \alpha(n)) and \Omega(n^2) for a 2-centre, where \alpha(n) denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2-centre of C: the 1-centre can be found in optimal time O(n \log n) when the distance function between mobile clients is known or O(n^2) when the function must be calculated, and a 2-centre can be found in time O(n^2 \log n). These algorithms lend themselves to implementation within the framework of kinetic data structures, resulting in structures that are compact, efficient, responsive, and local.
Fichier non déposé

Dates et versions

lirmm-00189505 , version 1 (21-11-2007)

Identifiants

  • HAL Id : lirmm-00189505 , version 1

Citer

Stéphane Durocher, Christophe Paul. Kinetic Maintenance of Mobile k-Centre in Trees. ISAAC'07: 18th International Symposium on Algorithms and Computation, 2007, Sendei, Japan. pp.341-352. ⟨lirmm-00189505⟩
61 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More