Computer Science – Computational Geometry
Scientific paper
2002-09-30
Computational Geometry: Theory and Applications, 25 (2003), 117-138.
Computer Science
Computational Geometry
28 pages, 14 figures, Latex, to appear in Computational Geometry - Theory and Applications
Scientific paper
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 imposed by the manufacturing process, we obtain quite different results. In particular, we study the variant of the carpenter's ruler problem in which there is a restriction that only one joint can be modified at a time. For a linkage that does not self-intersect or self-touch, the recent results of Connelly et al. and Streinu imply that it can always be straightened, modifying one joint at a time. However, we show that for a linkage with even a single vertex degeneracy, it becomes NP-hard to decide if it can be straightened while altering only one joint at a time. If we add the restriction that each joint can be altered at most once, we show that the problem is NP-complete even without vertex degeneracies. In the special case, arising in wire forming manufacturing, that each joint can be altered at most once, and must be done sequentially from one or both ends of the linkage, we give an efficient algorithm to determine if a linkage can be straightened.
Arkin Esther M.
Fekete Sandor P.
Mitchell Joseph S. B.
No associations
LandOfFree
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-694004