Efficient Segment Folding is Hard

12/21/2020
by   Takashi Horiyama, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset