Rectilinear static and dynamic discrete 2-center problems Academic Article uri icon


  • In this paper we consider several variants of the 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 versions of the problem (i.e. points of S are allowed to be inserted or deleted) and also consider the problem in fixed d, d ≥ 3 dimensional space. For the static version in the plane we give an optimal algorithm.

publication date

  • January 1, 1999