Multi-dimensional dynamic facility location and fast computation at query points Academic Article uri icon


  • We present O(nlogn) 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).

publication date

  • January 1, 2009