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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00189505
Contributor : Christophe Paul <>
Submitted on : Wednesday, November 21, 2007 - 10:46:03 AM
Last modification on : Wednesday, August 28, 2019 - 1:34:00 PM

Identifiers

  • HAL Id : lirmm-00189505, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

86