chitale@usceast.cs.scarolina.edu (Parijat Chitale) (08/18/90)
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. Thanx very much in advance, -Parijat ----------------------------------------------------------------------- God is really only another artist. He invented the giraffe, the elephant and the cat. He has no real style, He just goes on trying other things. -- Pablo Picasso Parijat Chitale [chitale@cs.scarolina.edu, ...!usceast!chitale] SUN Aug 19 10:46:47 EDT 1990
gordon@cs.tamu.edu (Dan Gordon) (08/19/90)
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?