An optimal approximation algorithm for the rectilinearm-center problem

Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove that there is no polynomial-time algorithm with an error ratio < 2 for the rectilinearm-center problem unless NP = P. A polynomial-time approximation algorithm with an error ratio of 2 is also proposed.This research work was partially supported by a grant from the National Science Council of the Republic of China under Grant NSC-77-0408-E007-03.