Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.graphics
Subject: Re: Minimum rectangles to cover a polygon
Message-ID: <7537@helios.TAMU.EDU>
Date: 19 Aug 90 02:37:12 GMT
References: <3400@usceast.UUCP>
Sender: usenet@helios.TAMU.EDU
Organization: Computer Science Department, Texas A&M University
Lines: 13

In article <3400@usceast.UUCP> chitale@usceast.cs.scarolina.edu (Parijat Chitale) writes:
>I am looking for an algorithm to cover a given polygon (co-ordinates of
>all the vertices are known) by a minimum number of rectangles.  I have
>seen algorithms to deal with covering of polygons with rectangles but 
>have not come across one that would generate a minimal covering.
>Any references about this, or any suggestions are really appreciated.

What are the conditions for this "covering"? As you stated them, one
rectangle is enough. I'm sure you have something else in mind.

I suspect that you mean that all rectangles are of the same pre-determined
size, but are there other restrictions - for example, can you rotate a
rectangle?