Optimizing squares covering a set of points
We investigate three kinds of optimization problems regarding n points in the 2-dimensional plane that need to be enclosed by squares. (1) Find a given number of squares that enclose all the points, minimizing the size of the largest square used. (2) Problem (1) with the additional condition that the center of each enclosing square must lie on one of the two given axis-parallel lines, which are either parallel or perpendicular. (3) Enclose the maximum number of points, using a specified number of squares of a fixed size. We propose different techniques to solve the above problems in cases where squares are axis-parallel or of arbitrary orientation, disjoint or overlapping. All the algorithms we use run in time that is a low-order polynomial in n, and improve upon the previous algorithms, if any.
facility location point covering by squares k-center problem