Kinetic maintenance of mobile kk-centres on trees

Given a set PP of points (clients) on a weighted tree TT, a kk-centre of PP corresponds to a set of kk points (facilities) on TT such that the maximum graph distance between any client and its nearest facility is minimised. We consider the mobile  kk-centre problem on trees. Let CC denote a set of nn mobile clients, each of which follows a continuous trajectory on a weighted tree TT. We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of CC. When each client in CC moves with linear motion along a path on TT, the motions of the corresponding 1-centre and 2-centre are piecewise linear; we derive a tight combinatorial bound of Θ(n)Θ(n) on the complexity of the motion of the 1-centre and corresponding bounds of O(n2α(n))O(n2α(n)) and Ω(n2)Ω(n2) for a 2-centre, where α(n)α(n) denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2-centre of CC: the 1-centre can be found in optimal time O(nlogn)O(nlogn) and a 2-centre can be found in time O(n2logn)O(n2logn). These algorithms lend themselves to implementation within the framework of kinetic data structures. Finally, we examine properties of the mobile 1-centre on graphs and describe an optimal unit-velocity 2-approximation.