Efficient segment folding is hard

Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, Katsuhisa Yamanaka

Research output: Contribution to journalJournal articleResearchpeer-review

1 Downloads (Pure)

Abstract

We introduce a computational origami problem which we call the segment folding problem: given a set of n line-segments in the plane the aim is to make creases along all segments in the minimum number of folding steps. Note that a folding might alter the relative position between the segments, and a segment could split into two. We show that it is NP-hard to determine whether n line segments can be folded in n simple folding operations.
Original languageEnglish
Article number101860
JournalComputational Geometry
Volume104
Number of pages19
ISSN0925-7721
DOIs
Publication statusPublished - 2022

Keywords

  • Computational origami
  • NP-hardness
  • Simple folds
  • Segment folding

Fingerprint

Dive into the research topics of 'Efficient segment folding is hard'. Together they form a unique fingerprint.

Cite this