We present a deterministic kinetic data structure for the facility location problem
that maintains a subset of the moving points as facilities such that, at any point
of time, the accumulated cost for the whole point set is at most a constant factor
larger than the optimal cost. Each point can change its status between client and
facility and moves continuously along a known trajectory in a d-dimensional Euclidean
space, where d is a constant.
Our kinetic data structure requires O(n(log^d(n) + log(nR))) space, where
R := (max_(p_i \in P){f_i} max_(p_i \in P){d_i}) / (min_(p_i \in P){f_i} min_(p_i \in P){d_i}),
P = { p_1, p_2, ... , p_n } is the set of given points, and f_i, d_i are the
maintenance cost and the demand of a point p_i, respectively. In case that each
trajectory can be described by a bounded degree polynomial, we process
O(n^2 log^2(nR)) events, each requiring O(log^(d+1)(n) log(nR)) time and O(log(nR))
status changes. To the best of our knowledge, this is the first kinetic data
structure for the facility location problem.