Abstract | ||
---|---|---|
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^{3}) time using O(n^{2}) 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. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1109/ICCTA.2007.45 | Inf. Process. Lett. |
Keywords | Field | DocType |
set theory,optimization,optimization problem,computational complexity,wireless communication,very large scale integration,computational geometry | Space time,Discrete mathematics,Combinatorics,Information processing,Computational geometry,Rectangle,Optimization problem,Mathematics | Conference |
Volume | Issue | ISBN |
109 | 16 | 0-7695-2770-1 |
Citations | PageRank | References |
7 | 0.52 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chandan Saha | 1 | 227 | 16.91 |
Sandip Das | 2 | 256 | 48.78 |