Deciding if a single 3D shape tiles space perfectly is impossible
Tiling 3D by Translates of a Single Polycube is Undecidable
Computational Geometry
Summary
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.
What this means in practice
- •For computational geometry developers: Know that algorithms cannot always decide if a single 3D shape tiles space without gaps or overlaps when translated.
- •For 3d puzzle designers: Understand inherent limits in designing infinite 3D tiling puzzles from a single shape, informing puzzle complexity and feasibility.
A theory result. No direct application yet.
Authors
Erik D. Demaine, Stefan Langerman
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$.