loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
International Conference on Computing: Theory and Applications (ICCTA'07)
Covering a Set of Points in a Plane Using Two Parallel Rectangles
Kolkata, India
March 05-March 07
ISBN: 0-7695-2770-1
Chandan Saha, Indian Institute of Technology, India
Sandip Das, Indian Statistical Institute, India
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.
Citation:
Chandan Saha, Sandip Das, "Covering a Set of Points in a Plane Using Two Parallel Rectangles," iccta, pp.214-218, International Conference on Computing: Theory and Applications (ICCTA'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.