Covering a Set of Points in a Plane Using Two Parallel Rectangles

In this paper we consider the problem of finding two parallel rectangles in arbitrary orientation for covering a given set of n points in a plane, such that the area of the larger rectangle is minimized. We propose an algorithm that solves the problem in O(n³) time using O(n²) space. Without altering the complexity, our approach can be used to solve another optimization problem namely, to minimize the sum of the areas of two arbitrarily oriented parallel rectangles covering a given set of points in a plane