How to find minimal amount of subdivisions

Question

Hi,

Imagine you have a canvas and in this canvas there are already some objects. How can you find the minimal way to cover the "uncovered" area with squares, not overlaying each other, completely filling the canvas.

In my case the "canvas" is a html-div container and the objects are nested div-containers. Could look like this: http://www.encodechain.com/demo/200908_optimize.png On the left there's the "start" and on the right there's on possible first "step"...

I know that there's an algorithm for this, but currently I can't remember the name.

Maybe you could help me out.

Thanks

Answer 1

Packing Problem

Knapsack Problem

And an article on solving 2d packing problem

Answer 2

The best I could find was this paper: Tiling a rectangle with the fewest squares. The paper is an interesting read, though at times it delves deep into theory territory with talk of "universal constants". I am not certain whether the question of "can a rectangle of size m by n be tiled with k squares" is NP-complete. As noted in another response, your question resembles packing problems which are NP-complete. And, of course, your problem is a generalization of the one addressed in this paper, since you are dealing with non-rectangular areas. You could start by breaking your area up into the minimum number of rectangles, another interesting problem in itself. And finally, even if you could do that efficiently, I'm not sure if tiling those rectangles optimally would result in an overall optimal tiling.

As the author notes, a greedy algorithm is a good place to start: just put down the biggest square you can until the area is full.