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.
