Kinetic Maintenance of Mobile k-Centres in Trees

Christophe Paul 1, 2 Stéphane Durocher 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a set P of points (clients) on a weighted tree T, the k-centre of P corresponds to a set of k points (facilities) on T such that the maximum graph distance between any client and its nearest facility is minimized. We consider the mobile k-centre problem on trees. Let C denote a set of n mobile clients, each of which follows a continuous trajectory on 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, the motions of the corresponding 1-centre and 2-centre are piecewise linear; we derive a tight combinatorial 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 the 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 :
Rapport
[Research Report] RR-06057, LIRMM. 2006, pp.16
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00118610
Contributeur : Christophe Paul <>
Soumis le : vendredi 16 février 2007 - 18:59:38
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : jeudi 20 septembre 2012 - 15:32:13

Fichier

Identifiants

  • HAL Id : lirmm-00118610, version 1

Collections

Citation

Christophe Paul, Stéphane Durocher. Kinetic Maintenance of Mobile k-Centres in Trees. [Research Report] RR-06057, LIRMM. 2006, pp.16. 〈lirmm-00118610〉

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

115