pipette
ESEspañol

Pinch-Free Orientations of Polyomino Grid Graphs

James Fox, Mirela Damian

Preprint

In the authors' words

We study lattice-based collective construction of a target polyomino on the integer grid, where robots place unit square blocks subject to two physical constraints: the partial structure must remain connected at all times, and no placement may create an unfillable one-cell gap. We present a wavefront sweep algorithm that computes a dependency structure satisfying the local conditions required for safe assembly. Given a list of n cells sorted lexicographically by coordinates, the orientation can be computed in O(n) time using O(n) auxiliary space.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 12 pages, 4 figures