Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: An Algorithmic Study of Manufacturing Paperclips and Other Folded
  Structures   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.

35
The categories of this paper are: mtrl-th
37
The categories of this paper are: supr-con
26
The categories of this paper are: bayes-an
25
The categories of this paper are: patt-sol
9
The categories of this paper are: nlin
24
The categories of this paper are: dg-ga
2
The categories of this paper are: math
27
The categories of this paper are: comp-gas
30
The categories of this paper are: q-alg
12
The categories of this paper are: nucl-th
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th
14
The categories of this paper are: math-ph
33
The categories of this paper are: plasm-ph
31
The categories of this paper are: ao-sci
18
The categories of this paper are: econ