Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
In case no satisfying answer comes forth here after a few days, consider reposting to cs.SE. – Raphael May 23 '12 at 11:00
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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