Algorithms for Manufacturing Paperclips and Sheet Metal Structures

Esther M. Arkin, Sándor P. Fekete, and Joseph S. B. Mitchell

folding, carpenter's rule conjecture, geometric algorithms, polygons, NP-completeness

We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting wire structure (a "carpenter's ruler") can be straightened, a problem that was open for several years and has only recently been solved in the affirmative.

If we impose some of the constraints that are present in industrial manufacturing, we get quite different results. In particular, we show that it is NP-complete (in the weak sense) to decide if a final configuration (simple chain in the plane, or simple polyhedral surface) is obtainable from a straight wire or flat sheet, using "all-or-nothing" folds, while keeping the structure simple (non-self-intersecting). (Each bend along a crease is made once, from the initial (flat) state to the final desired angle.) We also show that it is NP-complete to determine if a polygonal chain can be straightened, if the chain is allowed to have a vertex degeneracy, and only one joint can be opened at a time (allowing partial openings).

If we are required to make bends sequentially from one or both ends of the wire, as is often the realistic situation in wire forming manufacturing, we show that the problem becomes easier. We give efficient algorithms for these cases.

Download as [PDF] [ps.gz]