Back to Search
Start Over
COVERING A POINT SET BY TWO DISJOINT RECTANGLES.
- Source :
-
International Journal of Computational Geometry & Applications . Jun2011, Vol. 21 Issue 3, p313-330. 18p. 7 Diagrams. - Publication Year :
- 2011
-
Abstract
- Given a set S of n points in the plane, the disjoint two-rectangle covering problem is to find a pair of disjoint rectangles such that their union contains S and the area of the larger rectangle is minimized. In this paper we consider two variants of this optimization problem: (1) the rectangles are allowed to be reoriented freely while restricting them to be parallel to each other, and (2) one rectangle is restricted to be axis-parallel but the other rectangle is allowed to be reoriented freely. For both of the problems, we present O(n2log n)-time algorithms using O(n) space. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 21
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 61931231
- Full Text :
- https://doi.org/10.1142/S0218195911003676