Kinetic Maintenance of Mobile k-Centres in Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports (Research Report) Year : 2006

Kinetic Maintenance of Mobile k-Centres in Trees

Christophe Paul
Stéphane Durocher
  • Function : Author
  • PersonId : 836943

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

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00118610 , version 1

Cite

Christophe Paul, Stéphane Durocher. Kinetic Maintenance of Mobile k-Centres in Trees. [Research Report] RR-06057, LIRMM. 2006, pp.16. ⟨lirmm-00118610⟩
115 View
242 Download

Share

Gmail Facebook X LinkedIn More