Papers for

3d puzzle designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Deciding if a single 3D shape tiles space perfectly is impossible

Tiling 3D by Translates of a Single Polycube is Undecidable

Abstract: We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. We reduce from Wang tiling using the decorated two-prime Sudoku construction of Greenfeld and Tao and a cyclic encoding adapted from OpenAI's 3D aperiodic tile, and apply a reduction of Kim to make the prototile connected (via faces). Dimension three is optimal: translational monotiling is known to be decidable in $\mathbb{Z}^2$ and for a single (possibly disconnected) polyomino in $\mathbb{R}^2$.

Thu 8 OctComputational Geometry

The gist

This work shows that it is impossible to create a method that always decides if a single connected 3D shape can fill all of three-dimensional space by shifting it around. They prove this by linking the problem to known complex puzzles called Wang tilings. Interestingly, in two dimensions, this decision problem is already solved, but the jump to three dimensions makes it undecidable. The authors used advanced mathematical constructions to achieve this proof.

Open → 2610.12392v1