Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00118610
Contributor : Christophe Paul <>
Submitted on : Friday, February 16, 2007 - 6:59:38 PM
Last modification on : Wednesday, August 28, 2019 - 1:34:00 PM
Long-term archiving on: : Thursday, September 20, 2012 - 3:32:13 PM

Identifiers

  • HAL Id : lirmm-00118610, version 1

Collections

Citation

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

Share

Metrics

Record views

251

Files downloads

336