Kinetic Maintenance of Mobile k-Centre in Trees

Stéphane Durocher 1 Christophe Paul 2, 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Communication dans un congrès
ISAAC'07: 18th International Symposium on Algorithms and Computation, 2007, Sendei, Japan. pp.341-352, 2007, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00189505
Contributeur : Christophe Paul <>
Soumis le : mercredi 21 novembre 2007 - 10:46:03
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00189505, version 1

Collections

Citation

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, 2007, Lecture Notes in Computer Science. 〈lirmm-00189505〉

Partager

Métriques

Consultations de la notice

48