2
$\begingroup$

There is a side problem in my research that I believe should be a known problem. I do not want to spend lots of time on a problem that already has been studied, but I do not have a name for the problem to search for it. I hope someone can help. The precise definition can be found on http://imgur.com/goKKuSQ. Here I explain it in an informal language.

Problem definition:

There are two types of objects (say red and blue pieces) on a finite discrete 2-D space (the space is a closed subset of ZxZ). Number and locations of the pieces are arbitrary. Two pieces on the same coordinate are considered as one. It is not possible for a red piece and a blue piece to co-exist at the same coordinate.

In this space, we can define a rectangle by the coordinate of its upper-left and lower-right corners. The size and location of a rectangle can be anything but it is always parallel to X and Y axis.

I am looking for an algorithm to find the minimum number of rectangles that cover one type of the objects (say the blue pieces) only. Every and each blue piece should be inside or at the border of one or more rectangles, and no red piece can be on the border or inside any rectangle. The algorithm should return the coordinates of all such rectangles.

So, have you heard of this problem before? The first correct answer(s) will surely be acknowledged in my thesis.

Edit: I am searching for an algorithm of complexity smaller than exponential. The exhaustive search took forever to run and I had to stop the program. Also Evolutionary methods are not a good choice because of their long running time.

$\endgroup$
1
$\begingroup$

This sounds like the minimum rectangle cover problem.

Given an orthogonal polygon with holes, find the minimum number of rectangles needed to cover the interior of the polygon without covering any of the holes.

In your case, the red points mark the holes, and the blue points mark the interior of the polygon(s). In general, two blue regions might be disconnected, but then the minimum equals the sum of the minimum covers for the two disconnected regions.

Your problem can be easily mapped to the rectangle cover problem, and conversely the rectangle cover problem can be mapped to your problem assuming that all vertices of the polygon are on a grid, which can be assumed w.lo.g.

The bad news is that the minimum rectangle cover is NP-hard. It's also fairly hard to approximate in general (the best current approximation ratio is $O(\sqrt{\log n})$. However, if you had more information about the red and blue points, it's possible you might fall into one of the many special cases of rectangle cover that are easier to solve.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.