Multi-dimensional dynamic facility location and fast computation at query points

We present O(nlogn) time algorithms for the minimax rectilinear facility location problem in R¹ and R². The algorithms enable, once they terminate, computing the cost of any given query point in O(logn) time. Based on these algorithms, we develop a preprocessing procedure which enables solving the following two problems: Fast computation of the cost of any query point in Rd, and fast solution for the dynamic location problem in R² (namely, in the presence of an additional facility). Finally, we show that the preprocessing always gives a bound on the optimal value, which allows us in many cases to find the optimum fast (for both the traditional and the dynamic location problems in Rd for any d).