Cuboids - Githubissues

Hello there,

This past week I have been trying to tackle a certain problem : the computation of polycubes that fits inside a 3x3x3 cuboid. My work brought me to improve the Python code to make the computation faster but it also gave me an idea for the computation of polycubes of size n.

I consider as valid polycubes inside a cuboid of size (k1,k2,k3), those which span across the full extent of the cuboid in the 3 directions. I also put the constraint of k1>=k2>=k3 which does not change the final result because the problem is rotation invariant. The direct consequence is that the number of cubes (let me call that the rank) n of a valid polycube is bounded like so: k1+k2+k3-2 <= n <= k1k2k3. For the (3,3,3) cuboid, we have 7 <= n <= 27.

The generation of polycubes of each increasing rank inside a cuboid of a given shape is done starting from the rank 1 polycube at all possible positions inside the cuboid. The expansion function is modified since the output shape is the same as the input shape. Restricting the polycubes that fits inside the cuboid makes for a few optimizations in the computation: First, the shape is fixed so it does not need to be added to the packing of the cube. With Python, I have used the tobytes() function for an even faster packing but that does take 8 times as much space as needed. Second, the number of rotations in a cuboid is limited to 8 when k1=/=k2=/=k3 which is the most occuring general situation. In the case of the (3,3,3) cuboid, this is still 24 though. Third, the shape being fixed, a rotation is an index permutation operation and is made much faster (at least with numpy).

As a result, the number of polycubes of each rank tends to increase exponentially from 1 till n=k1k2k3/2 and then decreases exponentially to 1. The screening of invalid polycubes removes around 10% of the total after the expansion is over. By the way, the result for cuboids with k3>=2 and k1k2k3<=28 are available on my online viewer. https://asliceofcuriosity.fr/assets/polycube-viewer/index.html I'll make a PR soon with these improvements.

As for my contribution to the computation of polycubes of rank n, here is my idea. When you have all the polycubes in a cuboid of a certain shape (k1,k2,k3), you can compute part of the polycubes of the cuboids of shape (k1+1,k2,k3), (k1,k2+1,k3), (k1,k2,k3+1). Starting with the (1,1,1) cuboid, this makes for a graph of dependency where each cuboid can be computed by the expansion in different directions of three previous cuboids and can be expanded into three cuboids. So if one wants to generate and enumerate all of the polycubes of rank n, it needs to gather the polycubes of rank n from cuboids that satisfy the bounding equation and all of the cuboids before them in the graph up to a certain rank and so on. This dependency of cuboids and ranks is "easy" to compute and would split up the computation into several smaller chunks which would reduce file sizes, RAM usage and maybe computation time too.

I think that grouping together polycubes with the same shape would allow for many optimizations in terms of storage and computation. I have seen the idea mentioned in different ways across the posts from different people on different topics. I am in the process of implementing this idea in Python. The graph starts like this, with of all cuboids of the same depth in the graph on the same line and with the shape, the minimum and maximum rank for each cuboid: (1, 1, 1) 1 1 (2, 1, 1) 2 2 (3, 1, 1) 3 3 / (2, 2, 1) 3 4 (3, 2, 1) 4 6 / (4, 1, 1) 4 4 / (2, 2, 2) 4 8 (5, 1, 1) 5 5 / (3, 3, 1) 5 9 / (3, 2, 2) 5 12 / (4, 2, 1) 5 8 (6, 1, 1) 6 6 / (5, 2, 1) 6 10 / (4, 3, 1) 6 12 / (3, 3, 2) 6 18 / (4, 2, 2) 6 16 (4, 3, 2) 7 24 / (5, 2, 2) 7 20 / (7, 1, 1) 7 7 / (4, 4, 1) 7 16 / (3, 3, 3) 7 27 / (6, 2, 1) 7 12 / (5, 3, 1) 7 15

mikepound / opencubes

Cuboids #46