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 current optimal cost. At any point of time, the cost that arise for
a point depends on the status and the position of the point. In the case that a
point is currently a facility it causes maintenance cost, otherwise it causes
connection cost depending on its demand and its distance to the nearest facility.
In our scenario, 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 needs 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 the case that each
trajectory can be described by a bounded degree polynomial, the data structure
processes O(n^2 log^2(nR)) events, each requiring O(log(nR)) status changes and
O(log^(d+1)(n) log(nR)) time. This results in a total processing time of
O(n^2 log^(d+1)(n) log^3(nR)). To the best of our knowledge, this is the first
kinetic data structure for the facility location problem.