I'm looking for a 'covering rectangle with smaller rectangles' algorithm with the unique feature of being able to exclude some possible center points of rectangles. Basically, limiting the possible areas the smaller rectangles can be placed, while still having the algorithm try to solve for filling up the entire big rectangle with smaller rectangles (of a fixed size). Obviously this will sometimes result in the algorithm not succeeding, no possible solutions.

Has anyone seen anything like this or know how it would be developed?

somethings to keep in mind: 1. This problem can be optimally solved by simply placing the fixed size rectangle at every point that is allowed. This of course is too many rectangles, and I'm trying to accomplish this with the minimum amount of rectangles possible. the minimum amount can usually be determined by dividing the area of the big rectangle by the area of the smaller rectangle.

Example: a big rectangle with an area of 200. small rectangle with an area of 5. The smallest possible amount of rectangles to cover the area inside the big rectangle is 40 (200/5=40). If you limit the places you can put the rectangles, this number might grow, and the spacing might become uneven. I'm essentially asking for a way to solve this problem.

2.Coverage areas are not boxes, packing algorithms are not covering algorithms. coverage areas can overlap. box packing algorithms don't overlap.

  • $\begingroup$ In case no satisfying answer comes forth here after a few days, consider reposting to cs.SE. $\endgroup$ – Raphael May 23 '12 at 11:00

I cannot remark on "the unique feature of being able to exclude some possible center points of rectangles," a feature I do not understand. But I can offer some pointers to algorithms for covering with rectangles. First, an optimal cover is NP-hard: Culbertson and Reckhow, "Covering polygons is hard," 1988. Second, there are nevertheless published approximation algorithms: Berman and Dasgupta, "Complexities of Efficient Solutions of Rectilinear Polygon Cover Problems," 1994; Ramesh and Ramesh, "Covering Rectilinear Polygons with Axis-Parallel Rectangles," 1999. And you could use Google Scholar to find all later papers that reference these. Perhaps some of these algorithms can be adapted to include your unique features.


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.