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

We present O (n logn) time algorithms for the minimax rectilinear facility location problem in R-1 and R-2. 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 R-d, and fast solution for the dynamic location problem in R-2 (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 R-d for any d). (C) 2008 Elsevier B.V. All rights reserved.