Kinetic Maintenance of Mobile k-Centres in Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

Kinetic Maintenance of Mobile k-Centres in Trees

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

Résumé

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.
Fichier principal
Vignette du fichier
RR-06057.pdf (263.25 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00118610 , version 1 (16-02-2007)

Identifiants

  • HAL Id : lirmm-00118610 , version 1

Citer

Christophe Paul, Stéphane Durocher. Kinetic Maintenance of Mobile k-Centres in Trees. [Research Report] RR-06057, LIRMM. 2006, pp.16. ⟨lirmm-00118610⟩
119 Consultations
250 Téléchargements

Partager

Gmail Facebook X LinkedIn More