Paper by Erik D. Demaine

Reference:

Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, and Ryuhei Uehara, “Box pleating is hard”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 167–179.

BibTeX

@InProceedings{BoxPleatingHard_JCDCGG2015full,
  AUTHOR        = {Hugo A. Akitaya and Kenneth C. Cheung and Erik D. Demaine and Takashi Horiyama and Thomas C. Hull and Jason S. Ku and Tomohiro Tachi and Ryuhei Uehara},
  TITLE         = {Box pleating is hard},
  BOOKTITLE     = {Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015)},
  bookurl       = {http://www.kurims.kyoto-u.ac.jp/~takazawa/JCDCGG2015/},
  ADDRESS       = {Kyoto, Japan},
  MONTH         = {September 14--16},
  YEAR          = 2015,
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 9943,
  PAGES         = {167--179},

  doi           = {https://dx.doi.org/10.1007/978-3-319-48532-4_15},
  dblp          = {https://dblp.org/rec/conf/jcdcg/AkitayaCDHHKTU15},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-319-48532-4_15">SpringerLink</A>.},
  replaces      = {BoxPleatingHard_JCDCGG2015},
  papers        = {BoxPleatingHard_JCDCGG2015},
  withstudent   = 1,
}

Abstract:

Flat foldability of general crease patterns was first claimed to be hard for over twenty years. In this paper we prove that deciding flat foldability remains NP-complete even for box pleating, where creases form a subset of a square grid with diagonals. In addition, we provide new terminology to implicitly represent the global layer order of a flat folding, and present a new planar reduction framework for grid-aligned gadgets.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (6503k).

See information on file formats.

[Google Scholar search]

Related papers:

BoxPleatingHard_JCDCGG2015 (Box pleating is hard)