Kinetic Maintenance of Mobile k-Centres on Trees
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
- PDF / 470,102 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 79 Downloads / 168 Views
School of Computer Science, McGill University, Montr´eal, Canada [email protected] 2 CNRS & LIRMM, Montpellier, France [email protected]
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 Θ(n) on the complexity of the motion of the 1-centre and corresponding bounds of O(n2 α(n)) and Ω(n2 ) for a 2centre, where α(n) denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2centre 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(n2 ) when the function must be calculated, and a 2-centre can be found in time O(n2 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.
1
Introduction
Motivation. Finding a set of k points that are central to a collection of data points drawn from a metric space is a fundamental problem of geometry and data analysis. Within the context of facility location, this problem is commonly known as the k-centre problem; given a set P of points (clients) in a metric space S, a k-centre of P is a set of k points (facilities) such that the maximum distance from any client to its nearest facility is minimized. Two common choices for S are a Minkowski distance (typically 1 , 2 , or ∞ ) in Euclidean space and graph distance on a weighted graph. Recently, the k-centre problem has been explored under mobility. In one dimension, the mobile 1-centre problem reduces to maintaining the extrema of a set of mobile clients [1,2,4,16]. Natural generalizations of this problem to higher dimensions in Rd lead to the mobile Euclidean 1-centre [2,6,10], the mobile rectilinear 1-centre [2,6], and the kinetic convex hull [4,5,16]. Although some mobile k-centre problems can be modelled by motion in Euclidean space, several applications are better represented by motion on a graph. That is, the underlying
Research for this work was supported by NSERC.
T. Tokuyama (Ed.): ISAAC 2007, LNCS 4835, pp. 341–352, 2007. c Springer-Verlag Berlin Heidelberg 2007
342
S. Durocher and C. Paul
graph remains fixed while clients and facilities move along its edges and vertices. Examples include vehicles moving along a road network or mobile robots following defined routes in an industrial setting [7]. Although the static k-centre problem on graphs is well understood, the corresponding mobile problem remained unexplored. Any path in a weighted graph is isometric to a line segment; we generalize the motion of a single client on the line to motion on a path in a graph. That is, given a weighted graph G, each mobile client follows a continuous trajectory along the edges and vertices of G. Continuity and bounded veloc
Data Loading...
