Skip to Main content Skip to Navigation
Conference papers

Kinetic Maintenance of Mobile k-Centre in Trees

Stéphane Durocher Christophe Paul 1 
1 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Christophe Paul Connect in order to contact the contributor
Submitted on : Wednesday, November 21, 2007 - 10:46:03 AM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM


  • HAL Id : lirmm-00189505, version 1



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. ⟨lirmm-00189505⟩



Record views