Rectilinear static and dynamic discrete 2-center problems

In this paper we consider several variants of the rectilinear discrete 2-center problem. The problem is: Given a set S of n demand points and a set C of m supply points, find two ‘minimal’ axis-parallel squares (or rectangles) centered at the points of C that cover all the points of S. We present efficient solutions for both the static and dynamic version of the problem (i.e., the points of S are allowed to be inserted or deleted) and also consider the problem in d-dimensional space for fixed d, d ≥ 3. For the static version in the plane we give an optimal algorithm.