liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Folding Polyominoes into (Poly)Cubes
Institute for Software Technology, Graz University of Technology, Austria.
Department of Mathematics and Statistics, Swarthmore College, USA.
Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA.
Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA.
Show others and affiliations
2018 (English)In: International journal of computational geometry and applications, ISSN 0218-1959, Vol. 28, no 3, p. 197-226Article in journal (Refereed) Published
Abstract [en]

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°), 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.

Place, publisher, year, edition, pages
World Scientific Pub Co Pte Ltd , 2018. Vol. 28, no 3, p. 197-226
Keywords [en]
Folding; origami folding; polycubes; polyominoes
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-142561DOI: 10.1142/S0218195918500048Scopus ID: 2-s2.0-85056746982OAI: oai:DiVA.org:liu-142561DiVA, id: diva2:1153815
Available from: 2017-10-31 Created: 2017-10-31 Last updated: 2025-04-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Schmidt, Christiane

Search in DiVA

By author/editor
Schmidt, Christiane
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
International journal of computational geometry and applications
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 691 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf