Pinch-Free Orientations of Polyomino Grid Graphs
En palabras de los autores
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.
Resultado principalEl resumen no menciona limitaciones.
Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 12 pages, 4 figures