Kinetic facility location

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. 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 requires ${\displaystyle 𝒪\left(n\right({\log }^d\left(n\right)+\log (nR\left)\right))}$ space in total, where ${\displaystyle R:=\frac{\underset{p_i\in p}{max}{f}_i·\underset{p_i\in p}{max}{d}_i}{\underset{p_i\in p}{min}{f}_i·\underset{p_i\in p}{min}{d}_i}}$ , 𝒫={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 ${\displaystyle 𝒪\left(n^2{\log }^2\right(nR\left)\right)}$ events, each requiring ${\displaystyle 𝒪\left({\log }^{d+1}\right(n)·\log (nR))}$ time and ${\displaystyle 𝒪\left(\log (nR\right))}$ status changes.