Skip to Main content Skip to Navigation

Kinetic Maintenance of Mobile k-Centres in Trees

Christophe Paul 1 Stéphane Durocher 
1 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.
Document type :
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Christophe Paul Connect in order to contact the contributor
Submitted on : Friday, February 16, 2007 - 6:59:38 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Thursday, September 20, 2012 - 3:32:13 PM


  • HAL Id : lirmm-00118610, version 1



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



Record views


Files downloads