Minimal number of covering boxes for binary matrix

Question

I have a binary matrix n*m (0's and 1's). Problem is to cover all 1's with non-overlapping boxes whose elements are all 1.

Example:

1111
0110
0110

Box can be represent with coordinates and lengths in each coordinate (x,y,lx,ly). This example is covered with 2 boxes { (0,0,1,4), (1,1,2,2) }.

I'm looking how to find cover with minimal number of boxes.

Thanks

Answer 1

This problem is called partition of rectilinear polyhedron. There is a good answer on similar question biziclop posted in a comment.

Idea of algorithm is to reduce problem to maximum matching of bipartite graph (vertices are possible cuts.)

3D

My original problem was same topic in 3D. That version is shown to be NP-complete :-/

After some research, I implemented solution based on heuristic described in papers by Anuj Jain:

• Partitioning 3D Phantoms into Homogeneous Cuboids
• Partitioning 3D Regions into Cuboids

Answer 2

My problem domain is computational chemistry, and there we tackle huge multivariate problems. There are two general case global optimization algorithms that can be applied here that have also been successfully applied to systems containing tens of thousands of atoms:

a) genetic algorithms
http://en.wikipedia.org/wiki/Genetic_algorithm

b) simulated annealing
http://www.gnu.org/software/gsl/
ftp://ftp.alumni.caltech.edu/pub/ingber
http://www.taygeta.com/annealing/simanneal.html
http://www2.cs.uni-paderborn.de/cs/ag-monien/SOFTWARE/PARSA/
http://www.codeproject.com/KB/recipes/SimulatedAnnealing.aspx

Both algorithms have well respected public domain implementations and well understood optimality properties.