Constrained square-center problems Academic Article uri icon

abstract

  • . Given a set P of n points in the plane, we seek two squares whose center points belong to P , their union contains P , and the area of the larger square is minimal. We present efficient algorithms for three variants of this problem: In the first the squares are axis parallel, in the second they are free to rotate but must remain parallel to each other, and in the third they are free to rotate independently. 1 Introduction In this paper we consider the problems of covering a given set P of n points in the plane by two constrained (discrete) squares, under different conditions. We call a square constrained if its center lies on one of the input points. In particular, we solve the following problems: 1. Find two constrained axis-parallel squares whose union covers P , so as to minimize the size of the larger square. We present an O(n log 2 n)-time algorithm; its space requirement is O(n log n). 2. Find two constrained parallel squares whose union covers P , so as to minimize the siz...

publication date

  • January 1, 1998