direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 710-2001

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Algorithms for Manufacturing Paperclips and Sheet Metal Structures
Esther M. Arkin, Sándor P. Fekete, and Joseph S. B. Mitchell
primary: 68U05 Computer graphics; computational geometry
secondary: 68Q17 Computational difficulty of problems
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe