biggest cube problem (given set of bricks) - MathOverflow

biggest cube problem (given set of bricks)

2011-10-15T10:32:42Z

Input: set of bricks, each one is made of 1x1x1 cubes glued together face to face, like tetris pieces.

Problem: find the way of putting together those pieces to make a solid that contains biggest full cubical subsolid.

For example, the solid below contains a 2x2x2 cube

Is there any smart algorithm I could use in this kind of problem? The only solution that comes to mind is ordinary brute force. I'm looking for ideas for an accurate algorithm as well as an approximation algorithm.

Answer by Gerhard Paseman for biggest cube problem (given set of bricks)

2011-10-16T05:01:56Z

In general the problem should be NP-hard. While this may not be a reduction, I am thinking of trying to pack n^2 many 1 by 1 by n bins with 1 by 1 by k bricks, where k actually means many bricks of different sizes; if I am right, bin packing can be reduced to your problem.

If the bricks are of few types, it may be possible to construct quickly tiling solutions that allow one to get nice approximations. For example, 3 of the 7 blocks used to build a Soma cube each tile the 2x2x2 cube, so given any count of those 3 kinds of blocks, you can likely come within O(1) of the maximal cubical volume achievable using little more than arithmetic; if you can generate dissections of small cubes or prisms with your input bricks, you can then quickly decide which of many rectangular prisms are nicely buildable with the given tile set, and this can be used to approximate the maximal rectangular volume, or maximal cubical volume, as desired. Note that this does not contradict the above (idea for a) reduction because k in this instance is bounded from above by some small number.

Gerhard "Ask Me About System Design" Paseman, 2011.10.15

Answer by unknown (google) for biggest cube problem (given set of bricks)

2011-12-27T20:24:58Z

Look at dimension $n=2$. Then this reduces to finding a clique or independent set of given size $k$ which is NP-complete when the cubes (squares) are arbitrarily placed on $\mathbb{Z}^{2}$. Hence, this is NP-complete for higher dimensions in general case. It would be interesting to look at semidefinite relaxations of this problem (say call it as higher dimensional clique or independent set problem).

Having said that your problem is specific - in the sense - the cubes are not disjoint and the number of cubes in higher rows is lower than number of cubes in lower rows - for $n=3$, this specific case is most likely $O(N^{3})$ as it looks like scanning each row from bottom may suffice ($N$ is maximum of rows in all dimensions).