# Covering area algorithm?

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.

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