CS Paper Radar

Polyominoes Folding into Four and Five Distinct Boxes

Erik D. Demaine, Toshihiro Shirakawa, Conner Silverstein, Reed Silverstein, Michael Tardibuono, Ryuhei Uehara

cs.CG ·submitted 2026-11-03 03:28 UTC · v1

Abstract

We present new results on polyomino nets that fold into four or five distinct boxes. With the help of AI, we first found examples with areas 532 and 2128, respectively. We analyze these examples and reduce their areas to 178 and 358, respectively. We also generalize the construction of the five-box net and show that infinitely many polyomino nets fold into five distinct boxes.

Comment
13 pages, 9 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Polyomino Nets Covering Three Different Boxes of Area 106 and Related Results

cs.CG ·2026-08-20 ·Erik D. Demaine, Jenny Diomidova, Nicole Jacobus, Landon Kryger, Matthew T. Parker +3 more
unusual similarity 0.78
Abstract · Fix Figure 3

We present new results for polyomino nets that fold into 2 and 3 different cuboids through a computer search. The main result is the finding of 40 nets that fold into all three different cuboids with a surface area of 106. The secondary results are the finding of infinite families of nets that fold into three cuboid shapes, and the calculation of the number of common nets between smaller cuboids. The algorithms used to make the searches feasible will also be explained. The algorithms include taking advantage of some hidden structures in the nets that fold into the Nx1x1 cuboids, taking advantage of how a lot of nets fold into cuboid shapes in a 'striped' way, and using a variant of Redelmeier's algorithm. The paper ends with open questions that encourage the reader to broaden our collective understanding of the subject of creating polyomino nets.

0.43

Pinch-Free Orientations of Polyomino Grid Graphs

cs.CG ·2026-10-21 ·James Fox, Mirela Damian
similarity 0.54
Abstract · 12 pages, 4 figures

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.

0.30

Counting Polyominoes, Revisited: Corrigendum and Addendum

cs.DM ·2026-10-07 ·Gill Barequet, Gil Ben-Shachar
publishedunusualhighly cited similarity 0.53
Abstract

This is a Corrigendum and Addendum to Algorithmica paper (2026) 88:51.

0.65

Tiling 3D by Translates of a Single Polycube is Undecidable

cs.CG math.COmath.MG ·2026-10-08 ·Erik D. Demaine, Stefan Langerman
theory similarity 0.51
Abstract · 7 pages, 1 figure, 1 table

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$.

0.43

Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete

cs.CC ·2026-10-30 ·Qiuyu Chen, Baao Xie
theory similarity 0.51
Abstract

An important question in counting complexity is whether exact counting can remain hard under restrictions that make feasibility easy. Tilings of squares by a fixed family of polyominoes provide a stringent test of this question, since tileability is polynomial-time decidable and the only varying input is a binary-encoded side length. We prove that there exists a fixed finite family of connected polyominoes for which counting translation-only square tilings is #EXP-complete under polynomial-time metric reductions, while the counting function belongs to #E. The resulting separation reveals that solution multiplicities can retain computational information that feasibility alone cannot capture. The proof develops a two-stage numerical isolation technique that combines a boundary-amplified Wang system with a rigid geometric compiler to recover accepting-computation counts while controlling all noncanonical tilings.

0.22

Restless Guards: Robust Guarding of Polyominoes

cs.CG cs.DS ·2026-10-15 ·Linda Kleist, Ramin Kosfeld, Christian Rieck
similarity 0.50
Abstract · 34 pages, 33 figures

The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full coverage of the gallery shall be ensured despite locational uncertainty of the guards. We study this problem for polyominoes under rectangular visibility, where a $k$-restless guard assigned to a cell may move to any cell within distance at most $k$. While all polyominoes are guardable for $k\in\{0, 1\}$, the same is not true for all $k\geq 2$. However, for a given polyomino $P$ and integer $k$, we present an algorithm that identifies a $k$-restless guard set of $P$ in polynomial time, or decides that no such set exists. For the cases $k\in\{0,1\}$, where $k$-restless guard sets always exist, we provide tight worst-case bounds on the number of $k$-restless guards that are always sufficient and sometimes necessary to guard a hole-free polyomino with $n$ vertices or $m$ cells. Moreover, we show that computing a minimum guard set is NP-hard. Complementing the hardness, we provide polynomial-time algorithms for solving the problem optimally for histograms, and leverage this to obtain a $20k$-approximation for polyominoes without holes.

0.19

Optimal Polyomino Fences

cs.CG math.COcs.DM ·2026-11-12 ·Alexis Langlois-Rémillard, Mia N. Müßig, Helmut Podhaisky, Erika Roldan, Günter Rote +5 more
theory similarity 0.50
Abstract · 56 pages, 38 figures

The $n$-omino fence problem asks how many cells can be surrounded by placing every $n$-omino exactly once in the grid. We present a new dynamic programming approach for this problem, allowing us to prove optimality for the pentomino and hexomino fence and to classify all possible pentomino orders by optimal area. For the first time we also provide strong heuristic solutions and upper bounds for all fences up to $n = 15$, after which we even approximate the $500$-omino fence with computational experiments. Finally, we generalize the problem to 3D, where we prove optimality for pentacubes and derive heuristic solutions for hexacubes and heptacubes.

0.30

Stacking Stars: Minimum-Area Packing with and without Rotation

cs.CG cs.DS ·2026-11-04 ·Mikkel Abrahamsen, Jacobus Conradi, Arindam Khan, Jack Stade, Sampson Wong +2 more
similarity 0.47
Abstract · 52 pages, 35 figures

We study the problem of packing a given set of polygons into a minimum-area convex container, that is, placing them without overlap so as to minimize the area of their convex hull. Every previously known polynomial-time algorithm with a nontrivial approximation guarantee for packing polygons with arbitrary edge orientations required the polygons to be convex. In fact, an algorithm was not even known when every input polygon was a quadrilateral. We obtain such algorithms for the entire class of star-shaped polygons with unrestricted combinatorial complexity. The stars may be just translated or also rotated. In either case, we give an $O(\log n)$-approximation algorithm, where $n$ is the number of stars. Likewise, we get $O(\log n)$-approximation algorithms for bin and strip packing, assuming that the diameter of the stars is at most some (small) constant. Previous approximation algorithms for polygon packing focused on convex objects, and the analysis always relied on a density argument, i.e., if the area of the packed objects is at least a fraction $ρ$ of the area of the container, then we have a $(1/ρ)$-approximation. However, star-shaped polygons may need an arbitrarily large area to be packed, even when the total area of the stars approaches $0$ and each star has bounded diameter. This phenomenon prevents the use of density arguments. We instead establish a strong structural property about any packing: Even though the stars can fit together in complicated ways, we can reorganize them into simple stacks, replace these stacks by rectangles, and consider a packing of these rectangles. The rearrangement costs only a factor of $O(\log n)$, which stems from the number of size groups. We complement our algorithms by showing that both the translational and the rotational versions are APX-hard, even for constant complexity stars.

0.27