Folding Polyominoes into (Poly)Cubes

• Published in 2017
• Added on 2018-01-03

We study the problem of folding a polyomino $P$ into a polycube $Q$, allowing faces of $Q$ to be covered multiple times. First, we define a variety of folding models according to whether the folds (a) must be along grid lines of $P$ or can divide squares in half (diagonally and/or orthogonally), (b) must be mountain or can be both mountain and valley, (c) can remain flat (forming an angle of $180^\circ$), and (d) must lie on just the polycube surface or can have interior faces as well. Second, we give all the inclusion relations among all models that fold on the grid lines of $P$. Third, we characterize all polyominoes that can fold into a unit cube, in some models. Fourth, we give a linear-time dynamic programming algorithm to fold a tree-shaped polyomino into a constant-size polycube, in some models. Finally, we consider the triangular version of the problem, characterizing which polyiamonds fold into a regular tetrahedron.

Links

• http://arxiv.org/abs/1712.09317v1
• http://arxiv.org/pdf/1712.09317v1

Other information

BibTeX entry

@article{FoldingPolyominoesintoPolyCubes,
	key = {FoldingPolyominoesintoPolyCubes},
	type = {article},
	title = {Folding Polyominoes into (Poly)Cubes},
	author = {Oswin Aichholzer and Michael Biro and Erik D. Demaine and Martin L. Demaine and David Eppstein and S{\'{a}}ndor P. Fekete and Adam Hesterberg and Irina Kostitsyna and Christiane Schmidt},
	abstract = {We study the problem of folding a polyomino {\$}P{\$} into a polycube {\$}Q{\$}, allowing
faces of {\$}Q{\$} to be covered multiple times. First, we define a variety of
folding models according to whether the folds (a) must be along grid lines of
{\$}P{\$} or can divide squares in half (diagonally and/or orthogonally), (b) must be
mountain or can be both mountain and valley, (c) can remain flat (forming an
angle of {\$}180^\circ{\$}), and (d) must lie on just the polycube surface or can
have interior faces as well. Second, we give all the inclusion relations among
all models that fold on the grid lines of {\$}P{\$}. Third, we characterize all
polyominoes that can fold into a unit cube, in some models. Fourth, we give a
linear-time dynamic programming algorithm to fold a tree-shaped polyomino into
a constant-size polycube, in some models. Finally, we consider the triangular
version of the problem, characterizing which polyiamonds fold into a regular
tetrahedron.},
	comment = {},
	date_added = {2018-01-03},
	date_published = {2017-12-07},
	urls = {http://arxiv.org/abs/1712.09317v1,http://arxiv.org/pdf/1712.09317v1},
	collections = {Puzzles,Things to make and do,Geometry},
	url = {http://arxiv.org/abs/1712.09317v1 http://arxiv.org/pdf/1712.09317v1},
	urldate = {2018-01-03},
	year = 2017,
	archivePrefix = {arXiv},
	eprint = {1712.09317},
	primaryClass = {cs.CG}
}