Andrei Asinowski, Gill Barequet, Gil Ben-Shachar, Martha Carolina Osegueda,
and Günter Rote:
On the number of compositions of two polycubes
- Computing in Geometry and
Topology 3, no. 1 (2024), 4:1–4:18.
doi:10.57717/cgt.v3i1.41
→BibTeX
-
Preliminary version in: Extended Abstracts EuroComb 2021, European Conference on
Combinatorics, Graph Theory and Applications, Editors: Jaroslav
Nešetřil, Guillem Perarnau, Juanjo Rué, and Oriol
Serra, Springer-Verlag, 2021, pp. 71–77. doi:10.1007/978-3-030-83823-2_12
→BibTeX
Abstract
We provide almost tight bounds on the minimum and maximum possible numbers of
compositions of two polycubes of given total size, in two and higher
dimensions. In the plane, we reach a near-quadratic number of compositions. We
also provide an efficient algorithm (with some trade-off between time and
space) for computing the number of composition of two given polyominoes (or
polycubes).
Last update: October 27, 2021.