: I'm trying to find an algorithm to solve the general version of the
: "rectangle covering
: problem" of computational geometry.
: 1) The polygon is any general 2-D polygon. It is very common for a
: subset of
: polygons to be discussed in this context. For example, there are
: numerous papers
: discussing rectangle covering of "rectilinear" polygons (those with only
: 90 degree
: angles). There are also a few papers discussing "convex" polygons
: (those with
: interior angles of 90 degrees or more).
: 2) "With holes" means the polygon can have a polygonal "gap" in its
: interior. For
: example, if you transformed a donut into a 2-D polygon, you would have a
: with a hole. This presents challenges to the covering algorithm.
: 3) In general "covering" problems mean that the shapes can overlap,
: "partitioning" problems mean that the shapes cannot overlap. I'm
: interested in the
: covering problem.
: 4) While the "rectangle covering problem" is generally concerned with
: finding the
: minimum number of rectangles, I'm interested in any proposed solution
: (the fewer
: rectangles the better).
: I appreciate your response and look forward to your next post.
: :I recommend you say in more detail what the constraints are: what
: :"allowing holes means", whether the rectangles can overlap, etc.
The partitioning problem (according to your definition) is NP-Hard even
for simple variants like rectilinear polygons and axes-parallel rectangles.
There are approximation algorithms, but I can't say how implementable those
are. A recent reference is :
A. Kumar and R. Hariharan, ``Covering rectilinear polygons with axis-parallel
rectangles" ACM STOC '99.
I am not sure whether any solution for the covering problem (according to your
definition) exists if you don't allow your rectangles to go out of your polygon.
In other words, if you have an additional constraint that all the rectangles
should be inside the polygon that you are trying to cover. It is not difficult
to show that even for fairly simple polygons, you cannot cover them with
rectangles (axes-parallel or general) if you have this constraint.
If you allow your rectangles to go out of your polygon, one can give a simple
algorithm as follows :
Find the smallest bounding box for the polygon by computing the maximum x, minimum x,
maximum y and minimum y vertices. Now you have a rectangle which covers the
whole polygon. You can even partition it into smaller rectangles if you wish.
Hope this helps,