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 sum of the maintenance cost for the facilities and the connection cost
for the clients is at most a constant factor larger than the current optimal cost.
In our scenario, each point can open a facility and moves continuously along a known
trajectory in a d-dimensional Euclidean space where d is a constant.
Our kinetic data structure has a storage requirement of O(n(log^d(n) + log(nR))),
where n is the number of points and R is the ratio of the product of the maximum
maintenance cost and demand to the product of their corresponding minimum values.
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 only O(log(nR))
facility 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.