text:
# An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures

## 1 Introduction

The following is an algorithmic problem that arises in the study of the manufacturability of sheet metal parts: Given a flat piece, $`F`$, of sheet metal (or cardboard, or other bendable stiff sheet material), can a desired final polyhedral part, $`P`$, be made from it? The 2-dimensional version is the wire-bending (“paperclip”) problem: Given a straight piece, $`F`$, of wire, can a desired simple polygonal chain, $`P`$, be made from it? This problem also arises in the fabrication of hydraulic tubes, e.g., in airplane manufacturing.111We thank Karel Zikan for introducing to us the hydraulic tube bending problem at Boeing’s factory. In both versions of the problem, we require that any intermediate configuration during the manufacture of the part be feasible, meaning that it should not be self-intersecting. In particular, the paperclips that we manufacture are not allowed to be “pretzels” – we assume that the wire must stay within the plane, and not cross over itself. See Figure 1 for an illustration. We acknowledge that some real paperclips are designed to cross over themselves, such as the butterfly style of clip shown in the figure.

Our problem is one of automated process planning: Determine a sequence (if one exists) for performing the bend operations in sheet metal manufacturing. We take a somewhat idealized approach in this paper, in that we do not attempt to model here the important aspects of tool setup, grasp positions, robot motion plans, or specific sheet metal material properties which may affect the process. Instead, we focus on the precise algorithmic problem of determining a sequence for bend operations, on a given sheet of material with given bend lines, assuming that the only constraint to performing a bend along a given bend line is whether or not the structure intersects itself at any time during the bend operation.

Note that the problem of determining if a bend sequence exists that allows a structure to unfold is equivalent to that of determining if a bend sequence exists that allows one to fold a flat (or straight) input into the desired final structure: the bending operations can simply be reversed. For the remainder of the paper, we will speak only of unfolding or straightening.

### 1.1 Motivation and Related Work

Our foldability problem is motivated from process planning in manufacturing of structures from wire, tubing, sheet metal, and cardboard. The CAD/CAM scientific community has studied extensively the problem of manufacturability of sheet metal structures; see the thesis of Wang  for a survey. Systems have been built (e.g., PART-S  and BendCad ) to do computer-aided process planning in the context of sheet metal manufacturing; see also . See  for a motion planning approach to the problem of computing folding sequences for folding three-dimensional cardboard cartons. Considerable effort has gone into the design of good heuristics for determining a bend sequence; however, the known algorithms are based on heuristic search (e.g., A) in large state spaces; they are known to be worst-case exponential. (Wang  cites the known complexity as $`O(n!2^n)`$.)

Our work is also motivated by the mathematical study of origami, which has received considerable attention in recent years. In mathematics of origami, Bern and Hayes  have studied the algorithmic complexity of deciding if a given crease pattern can be folded flat; they give an NP-hardness proof. Lang  gives algorithms for computing crease patterns in order to achieve desired shapes in three dimensions. Other work on computational origami includes . A closely related problem is that of flat foldings of polyhedra. It is a classic open question whether or not every convex polytope in three dimensions can be cut open along its edges so that it unfolds flat, without overlaps. Other variants and special cases have been studied; see .

Finally, we are motivated by the study of linkage problems; in fact, in the time since this paper was first drafted, the carpenter’s ruler conjecture has been resolved by Connelly, Demaine, and Rote  and Streinu : Any (strongly) simple polygonal linkage with fixed length links and hinged joints, can be straightened while maintaining strong simplicity (i.e., without the linkage crossing or touching itself). (They also show related facts about linkage systems, e.g., that any simple polygonal linkage can be convexified.) In fact, Streinu  gives an algorithmic solution that bounds the complexity of the unfolding and is somewhat more general than the slightly earlier results of . These results imply that any (strongly simple) paperclip can be manufactured if one has a machine that can perform a sufficiently rich set of bending operations. For a recent overview of folding and unfolding, see the thesis of Demaine . Earlier and related work on linkages includes . Our hardness results are particularly interesting and relevant in light of these new developments, since we show that even slight changes in the assumptions about the model or the allowed input results in linkages that cannot be straightened, and it is NP-hard to decide if they can be straightened.

### 1.2 Summary of Results

We show that it is (weakly) NP-complete to determine if a given rectilinear polygonal linkage can be straightened, under the restriction that only one joint at a time is altered and each joint can be altered only once (so the joint must be straightened in a single bend operation). A consequence is that the more general sheet metal bending problem is hard as well, even in the case of parallel bend lines and an orthohedral structure $`P`$.

We prove that it is (weakly) NP-hard to determine if a given polygonal linkage can be straightened if there is a vertex degeneracy, in which two vertices coincide. Here we again assume that only one joint can be altered at a time, but we do not assume that a joint is altered only once, so we may make any number of bends at any particular joint.

We give efficient algorithms for determining if a given bend sequence is feasible, assuming only one joint is altered at a time, and for determining if certain special classes of bend sequences are feasible. In particular, we give an efficient ($`O(n\mathrm{log}^2n)`$) algorithm for determining if a polygonal linkage can be straightened using a sequential strategy, in which the joints are completely straightened, one by one, in order along the linkage. We also give efficient polynomial-time algorithms for deciding whether there is a feasible bend sequence that straightens joints in an order “inwards” from both ends or “outwards” towards both ends. (Such constrained bend sequences may be required for automated wire-bending machines.) These results will be made more precise in Section 4.

## 2 Preliminaries

The input to our problem is a simple polygonal chain (linkage), $`P`$, with vertex sequence $`(b_0,b_1,b_2,\mathrm{},b_{n+1})`$. The points $`b_0`$ and $`b_{n+1}`$ are the endpoints of the chain, and the $`n`$ vertices $`b_1,\mathrm{},b_n`$ are the bends (or joints). The line segments $`b_ib_{i+1}`$ are the edges (or links) of $`P`$. The edge $`b_ib_{i+1}`$ is a closed line segment; i.e., it includes its endpoints. We consider the chain $`P`$ to be oriented from $`b_0`$ to $`b_{n+1}`$, and we consider each edge of $`P`$ to have a left and a right side. Each bend $`b_i`$ has an associated bend angle $`\theta _i(0,2\pi ]`$, measured between the right sides of the two edges incident on $`b_i`$.

The chain $`P`$ is strongly simple if any two edges, $`b_ib_{i+1}`$ and $`b_jb_{j+1}`$, of $`P`$ that are not adjacent ($`ij`$) are disjoint and any two adjacent edges share only their one common endpoint. We say that $`P`$ is simple if it is not self-crossing but it possibly is self-touching, with a joint falling exactly on a non-incident edge or another joint; i.e., $`P`$ is simple if it is strongly simple or an infinitesimal perturbation of it is strongly simple.

We consider the chain $`P`$ to be a structure consisting of rigid rods as edges, whose lengths cannot change, connected by hinged joints. When a bend operation is performed at joint $`b_i`$, the bend angle $`\theta _i`$ is changed. Throughout this paper, we assume that the only bend operations allowed are single-joint bends, in which only one bend angle is altered at a time. We establish the convention that when a bend operation occurs at $`b_i`$, the subchain containing the endpoint $`b_0`$ remains fixed in the plane, while the subchain containing $`b_{n+1}`$ rotates about the joint $`b_i`$. This convention allows us to have a unique embedding of a partially or fully straightened chain in the plane.

A bend operation is complete if, at the end of the operation, the bend angle is $`\pi `$; we then say that the joint has been straightened. A bend operation that is not complete is called a partial bend. A sequence of bend operations is said to be monotonic if no bend operation increases the absolute deviation from straightness, $`|\theta _i\pi |`$, for a joint $`b_i`$. If all joints of $`P`$ have been straightened, the resulting chain is a straight line segment, $`F`$, of length $`_{i=0}^n|b_ib_{i+1}|`$, where $`|b_ib_{i+1}|`$ denotes the Euclidean length of segment $`b_ib_{i+1}`$. By our bend operation convention, one endpoint of $`F`$ is $`b_0`$, and $`F`$ contains the segment $`b_0b_1`$ (which never moves during bend operations).

For $`SB`$, we let $`P(S)`$, denote the partially straightened polygonal chain having each of the bends $`b_iS`$ straightened (to bend angle $`\pi `$), while each of the other bends, $`b_iS`$, is at its original bend angle $`\theta _i`$. Thus, in this notation $`P(B)=F`$ and $`P(\mathrm{})=P`$. We let $`P(S;i,\theta )`$, for $`1in`$ with $`iS`$, denote the chain in which each bend $`b_jS`$ is at bend angle $`\pi `$, bend $`b_i`$ is at angle $`\theta `$, and all other bends $`b_jS`$ are at their original bend angles $`\theta _j`$. We say that chain $`P(S)`$ or $`P(S;i,\theta )`$ is feasible if it is a simple chain.

We say that bend $`b_i`$ is foldable (or is a feasible fold) for $`P(S)`$ if $`P(S;i,\theta )`$ is feasible for all $`\theta `$ in the range between $`\pi `$ and $`\theta _i`$ (more precisely, for all $`\theta _i\theta \pi `$, if $`\theta _i<\pi `$, or for all $`\pi \theta \theta _i`$, if $`\theta _i>\pi `$). If $`b_i`$ is foldable, then it is possible to make a complete bend at $`b_i`$, meaning that the joint can be straightened in a single operation without causing the chain to self-intersect. We say that a permutation $`\sigma =(i_1,i_2,\mathrm{},i_n)`$ of the indices $`\{1,2,\mathrm{},n\}`$ is foldable for $`P`$ if, for $`j=1,2,\mathrm{},n`$, joint $`b_{i_j}`$ is foldable for $`P(\{b_{i_1},\mathrm{},b_{i_{j1}}\})`$, i.e., if $`P`$ can be unfolded into the straight segment $`F`$ using the bend sequence $`\sigma `$ (so that, by reversing the operations, $`P`$ can be manufactured from $`F`$ using the reverse of the bend sequence).

The Wire Bend Sequencing problem can be formally stated as: Determine a foldable permutation $`\sigma `$, if one exists, for a given chain $`P`$.

This paper studies the Wire Bend Sequencing problem for polygonal chains in the plane. We note, however, that our results have some immediate implications for the Sheet Metal Bend Sequencing problem, which is defined analogously for a polyhedral surface $`P`$ having a pattern $`B`$ of bend lines (creases), each of which must be straightened in order to flatten $`P`$ into a flat polygon $`F`$. Specifically, the hardness of the Sheet Metal Bend Sequencing follows from the hardness of the Wire Bend Sequencing, which can be seen as a special case of the sheet metal problem in which $`F`$ is a rectangle and the bend lines $`B`$ are all segments parallel to two of the sides of $`F`$ and extending all the way across $`F`$.

We give an example in Figure 1 of some common paperclip shapes, (a)–(c). We also show an example, (d), of a 5-link paperclip that cannot be straightened using complete bends, for any permutation $`\sigma `$ of the bends. Finally, we show an example of a 6-link paperclip for which the foldable permutations are $`\{(1,5,4,3,2),(1,5,4,2,3)\}`$; we show the sequence of bends, with the intermediate structures, for the permutation $`\sigma =(1,5,4,3,2)`$.

## 3 Hardness Results

### 3.1 Complete Bends

Our first result shows that if we require bends to be complete, as in our specification of the Wire Bend Sequencing problem, the problem of deciding if there is a feasible bend sequence is NP-complete.

###### Theorem 3.1

Wire Bend Sequencing is (weakly) NP-complete, even if $`P`$ is rectilinear.

Proof: We prove NP-completeness, even in the case that we are restricted to a special class of bend sequences, namely, those that can be written as the concatenation of up to four monotone subsequences of the index set $`\{1,\mathrm{},n\}`$. Below, we refer to each subsequence of bends as a monotone pass over the chain, going from one end to the other, performing a specified subset of complete bends.

Our reduction is from Partition: Given a set $`S`$ of $`n`$ integers, $`a_i`$, which sum to $`A=_ia_i`$, determine if there exists a partition of the set into two subsets each of which sums to $`A/2`$.

The key idea of our construction uses two components, as shown in Figure 2: One is a rigid “frame” that can only be unfolded if one end of the chain can be removed from within this frame. The other component is a “key” that encodes the partition instance. Collapsing the key is possible if and only if there is a partition of the integers into two sets of equal sum. The total number of segments will be $`\mathrm{}=26+4n`$; we write $`b_i`$ ($`i=0,1,\mathrm{},26+4n`$) for the vertices, and $`s_i=(b_{i1},b_i)`$ for the segments. For any point in time, we refer to the position of a joint $`b_i`$ by its coordinates $`(x_i,y_i)`$. When discussing some of the relative distances, we use $`d_{\mathrm{}}(b_i,b_j)=\mathrm{max}\{|x_ix_j|,|y_iy_j|\}`$.

More precisely, the frame consist of $`13`$ segments, $`s_1=(b_0,b_1),\mathrm{},s_{13}=(b_{12},b_{13})`$, as shown in the figure. Segment lengths are chosen such that the size of the frame is $`\mathrm{\Theta }(L)`$, with minimal coordinate differences $`d_{\mathrm{}}(b_0,b_{13})`$, $`d_{\mathrm{}}(b_1,b_{12})`$, $`d_{\mathrm{}}(b_2,b_{11})`$, $`d_{\mathrm{}}(b_3,b_{10})`$, $`d_{\mathrm{}}(b_4,b_9)`$, $`d_{\mathrm{}}(b_5,b_8)`$, $`d_{\mathrm{}}(b_6,b_7)`$ being $`\mathrm{\Theta }(\epsilon )`$, where $`\epsilon =1/(n^3L^2)`$. The “key” consists of $`13+4n`$ segments, $`s_{14}=(b_{13},b_{14})`$, $`\mathrm{},s_{26+4n}=(b_{25+4n},b_{26+4n})`$. For $`i=0,\mathrm{},4n+2`$, the “auxiliary” segments $`s_{15+4i}`$, $`s_{16+4i}`$, $`s_{17+4i}`$ have length $`\epsilon `$, while the “partition” segments $`s_{18+4i}`$ have length $`a_i`$. The long “positioning” segments $`s_{14}`$, $`s_{15}`$, $`s_{25+4n}`$, $`s_{26+4n}`$ have lengths $`L`$, $`L/3`$, $`L/3`$, and $`L3n\epsilon `$, respectively; they guarantee that the partition segments must have a particular relative position when removing the key. We choose the scale to be such that $`L/4>A`$, for technical reasons that will become clear later in the proof. As indicated in the figure, the initial position of each key segment $`s_i,i=14,\mathrm{},26+4n`$ has $`x`$-coordinate $`x_{13}`$ or $`x_{13}+\epsilon `$, with a horizontal distance of $`x_ix_4=\epsilon `$ or $`x_ix_4=2\epsilon `$ from $`s_4`$. Moreover, $`b_{14}`$ is positioned at a vertical distance of $`y_{14}y_4=n^2\epsilon =1/(nL^2)`$ above $`b_4`$.

The purpose of the auxiliary segments is as follows. As shown in Figure 2, we have two types of joints in the figure: the “ordinary” ones (indicated by solid black dots) form the frame and can only be accessed once. The “quadruple” ones (indicated by hollow dots in Figure 2) consist of the four simple joints at three consecutive auxiliary segments; they are found along the key as described. These quadruple joints make it possible to simulate opening and closing such a joint a limited number of times.

Now assume that there is a partition $`S=S_1\stackrel{}{}S_2`$, such that $`_{iS_1}a_i=_{iS_2}a_i`$. In order to see that the key can be removed from the frame we first convert it into the “stair” configuration shown in Figure 3: We make one monotone pass over the chain towards the key end, and straighten one ordinary joint per quadruple joint whenever this joint separates two segments from different $`S_i`$. Thus, segments corresponding to numbers in $`S_1`$ will be horizontal, while those for numbers in $`S_2`$ will be vertical. In order to keep the number of monotone passes limited to four, during this first pass we also straighten two ordinary joints per quadruple joint separating two segments from the same $`S_i`$, as shown in Figure 3(b).

Making a similar monotone pass, we can convert the stair into a “flat harmonica”, as shown in Figure 4, with segments from $`S_2`$ pointing “down”, i.e., $`y_i<y_{i1}`$, and segments from $`S_1`$ pointing “up”, i.e., $`y_i>y_{i1}`$. By assumption about the partition, the positions of endpoints $`b_{18}`$ and $`b_{18+4n}`$ satisfy $`d_{\mathrm{}}(b_{18},b_{18+4n})<3n\epsilon `$, and $`2L/33\epsilon <y_{13}y_{18}<2L/3+3\epsilon `$, i.e., both $`b_{18}`$ and $`b_{18+4n}`$ are roughly $`2L/3`$ below $`b_{13}`$. Altogether, the position of the last segment $`s_{26+4n}`$ of length $`L`$ in the chain will differ by at most $`O(n\epsilon )`$ from the vertical position of segment $`s_{14}`$, with all other segments strictly in-between. This collapsed structure can be rotated about $`b_{13}`$ without colliding with any frame segments. Then it is easy to open up the remaining frame (by straightening $`b_{12}`$, $`b_{11}`$, $`b_{10}`$, $`b_8`$, $`b_7`$, $`b_6`$, $`b_5`$, $`b_4`$, $`b_3`$, $`b_2`$, $`b_1`$ as one monotone pass, skipping $`b_9`$.) Finally, the resulting monotone chain can be straightened in one last monotone pass.

Conversely, assume now that the chain can be straightened. See Figure 5. It is clear that $`b_{13}`$ must be straightened before any other joint in the set $`\{b_1,\mathrm{},b_{12}\}`$. In order to avoid hitting vertex $`b_4`$ during this motion, any part of the key to the right and below $`b_{13}`$ must be strictly within the circle $`C`$ of radius $`r=\sqrt{(L+1/(nL^2))^2+\epsilon ^2}<L+2/(nL^2)`$ around $`b_{13}`$, where $`r`$ is the distance between $`b_{13}`$ and $`b_4`$ (see Figure 4.) The following technical arguments show that at this time, segment $`s_{26+4n}`$ has to be in a vertical position that basically coincides with $`s_{14}`$, which is only possible in case of a feasible partition.

When starting the rotation about $`b_{13}`$, $`s_{26+4n}`$ is an axis-parallel segment of length $`L3n\epsilon >L1/(nL^2)`$. The rigid frame and the closeness of $`b_{14}`$ and $`b_4`$ ensure that segment $`s_{26+4n}`$ cannot lie to the left of $`s_{14}`$, implying that $`s_{26+4n}`$ can only lie within the quarter circle of radius $`r`$ below and to the right of $`b_{13}`$ when $`b_{13}`$ is straightened.

Let $`b_{\mathrm{min}}`$ be one of the two points in $`\{b_{25+4n},b_{26+4n}\}`$ that is not further from $`b_{13}`$ than the other, and let $`b_{\mathrm{max}}`$ be the other point. If the vertical distance $`y_{13}y_{\mathrm{min}}`$ is greater than $`\sqrt{7/(nL)}`$, it follows that the Euclidean distance between $`b_{\mathrm{max}}`$ and $`b_{13}`$ is at least

$$\sqrt{\frac{7}{nL}+\left(L\frac{1}{nL^2}\right)^2}=\sqrt{\left(L+\frac{2}{nL^2}\right)^2+\frac{1}{nL}\frac{3}{n^2L^4}}>L+\frac{2}{nL^2}>r,$$

a contradiction to the assumption that $`s_{26+4n}`$ is fully contained in $`C`$. Now, using our assumption that $`L/4>A`$, we know that $`b_{25+4n}`$ and $`b_{14}`$ are connected by a polygonal chain of length strictly less than $`L/3+L/4+L/3=11L/12`$, implying that $`b_{25+4n}`$ has Euclidean distance at least $`L/12`$ from $`b_{13}`$, so $`b_{26+4n}=b_{\mathrm{min}}`$ and $`b_{25+4n}=b_{\mathrm{max}}`$. As $`b_{26+4n}`$ is within $`\sqrt{7/(nL)}`$ of $`b_{13}`$, it follows that $`b_{26+4n}`$ has Euclidean distance at least $`L\sqrt{7/(nL)}`$ from $`b_{14}`$. If $`s_{26+4n}`$ were horizontal, then the Euclidean distance between $`b_{25+4n}`$ and $`b_{14}`$ would be at least $`\sqrt{\left(L\sqrt{7/(nL)}\right)^2+(L1/(nL^2))^2}>11L/12`$, a contradiction. Hence, $`s_{26+4n}`$ must be vertical. Just as we derived for the vertical distance between $`b_{13}`$ and $`b_{26+4n}`$, it follows for the horizontal distance that $`x_{26+4n}x_{13}\sqrt{7/(nL)}1`$.

Now observe that when starting the rotation about $`b_{13}`$, all partition segments must be strictly between $`s_{14}`$ and the narrow strip between $`s_{14}`$ and $`s_{26+4n}`$, meaning that they are all vertical. Let $`S_1`$ be the set of “upwards” partition segments $`s_i`$ with $`y_i>y_{i1}`$, and $`S_2`$ be the set of “downwards” partition segments $`s_i`$ with $`y_i<y_{i1}`$. As $`|y_{24+4n}y_{15}|=\mathrm{\Theta }(n\epsilon )`$ and $`|y_{25+4n}y_{14}|=\mathrm{\Theta }(n^2\epsilon )`$, we conclude that the integral total length of upwards segments equals the integral total length of downwards segments.

This means that $`_{iS_1}a_i=_{iS_2}a_i`$, and we have a feasible partition. This completes the proof. $`\mathrm{}`$

### 3.2 Partial Bends

Now we consider the case in which each joint may be changed an arbitrary number of times during the straightening operations, while still making single-joint bends (bending only one joint at a time). This version of the problem is closely related to the carpenter’s ruler problem studied by . In the context of our study on folding, there may be the additional requirement of using only monotonic bend operations, e.g., to avoid work-hardening the wire, possibly causing it to break. We begin with the following observation about the sufficiency of monotonic single-joint bends; see also the discussion on p. 9 of Demaine’s thesis .

###### Theorem 3.2

Any strongly simple polygonal chain $`P`$ can be straightened using a finite number of monotonic single-joint bends.

Proof: Consider the set $`𝒮`$ of points in $`n`$-dimensional joint-angle space that correspond to strongly simple embeddings of the linkage. A single-joint bend corresponds to axis-parallel motion in joint-angle space. If self-touching is prohibited, $`𝒮`$ is an open set; note too that $`𝒮`$ is bounded. By Streinu’s result , there is an opening motion of the chain that consists of a finite number of individual monotonic moves. Such an opening motion corresponds to a path, $`\mathrm{\Pi }`$, in $`𝒮`$, comprised of a finite number of arcs, each corresponding to a monotonic move. Let $`\epsilon `$ be the Euclidean distance between path $`\mathrm{\Pi }`$ and the boundary of $`𝒮`$; since $`𝒮`$ is open, we know that $`\epsilon >0`$. Then we can replace each arc of the path $`\mathrm{\Pi }`$ with a finite sequence of axis-parallel moves of size $`\epsilon /2`$, yielding a straightening that uses single-joint bends. $`\mathrm{}`$

We will refer to a sequence of small individual moves that mimics an overall large-scale motion of several joints as “wiggly”, since the overall motion may be achieved through back-and-forth motions of individual segments that gradually change individual angles.

The following results show that allowing even a single point of self-incidence along the linkage changes the overall situation quite drastically.

###### Lemma 3.3

There are polygonal chains $`P`$ with a single vertex-to-vertex incidence that cannot be straightened using partial single-joint bends.

Proof: See Figure 6. The chain has eight joints (labeled $`b_0,\mathrm{},b_7`$) and seven segments (of the form $`s_i=(b_{i1},b_i)`$). The endpoint $`b_0`$ coincides with joint $`b_5`$. It is easily checked that none of the joints $`b_1,\mathrm{},b_4`$ can be changed without causing a self-intersection: Assume that there is a feasible motion of a joint $`b_i`$ with $`0<i<5`$. Then the points $`b_0`$ and $`b_5`$ would move away from each other along a circle around $`b_i`$. Without loss of generality, assume that $`b_5`$ remains in place, while $`b_0`$ is moving. Now consider the first such rotation that starts with $`b_0`$ and $`b_5`$ coinciding, and that avoids a crossing of $`s_1`$ with both $`s_5`$ and $`s_6`$. If $`b_0`$ moves clockwise around $`b_i`$, it is easy to see that the angle between $`(b_0,b_i)`$ and $`s_5`$ must be at least $`\pi /2`$ when starting the motion, or else $`s_1`$ and $`s_5`$ intersect. If $`b_0`$ moves counterclockwise around $`b_i`$, the same follows for the angle between $`(b_0,b_i)`$ and $`s_6`$. Therefore, the center of rotation must lie within the shaded region shown in the figure. (The cone to the left of $`b_5`$ is feasible for clockwise rotation, while the cone to the right of $`b_5`$ is feasible for counterclockwise roation.) However, none of the joints $`b_1,\mathrm{},b_4`$ lies inside of this feasible region. It follows that $`b_0,\mathrm{},b_5`$ form a rigid frame, as long as the angle at $`b_5`$ stays smaller than $`\pi /2`$.

On the other hand, it is easy to see that $`b_7`$ cannot be removed from the pocket formed by $`b_1`$, $`b_2`$, and $`b_3`$ if only the two remaining “free” joints $`b_5`$ and $`b_6`$ can be changed. The claim follows. $`\mathrm{}`$

If $`b_0`$ and $`b_5`$ have some positive distance, then the frame can be opened along the lines of the approach in  or  by gradually straightening $`b_5`$, $`b_6`$, $`b_1`$, $`b_2`$, and $`b_3`$, so that the “zig-zagging” part between $`b_0`$ and $`b_3`$ pushes left, while $`b_6`$ swings around $`b_5`$.

Using the frame as a gadget, we can show the following:

###### Theorem 3.4

It is NP-hard to decide if a polygonal chain $`P`$ with a single vertex-to-vertex incidence can be straightened by arbitrary partial single-joint bends.

Proof: The basic idea is similar to the one in Theorem 3.1 and also establishes a reduction of Partition. (Refer to Figure 7 for an overview.) As before, we write $`b_i`$ for the joints, and $`s_i=(b_{i1},b_i)`$ for the segments. We use the idea of the construction from Lemma 3.3 to construct a rigid frame, with the key corresponding to the free end of that chain. The frame has one end, $`b_0`$, of the polygonal chain wedged into the corner $`b_{13}`$, which has angle $`\phi \pi /2`$. Because of the degeneracy at $`b_{13}`$, none of the joints $`b_1,\mathrm{},b_{12}`$ can be moved individually without causing a self-intersection between $`b_0`$ and the chain in the neighborhood of $`b_{13}`$: Just like in the proof of Lemma 3.3, none of the joints $`b_1,\mathrm{},b_{12}`$ lies in the area of possible locations of feasible rotations. This continues to be the case while $`\varphi +\psi <\pi `$, i.e., while the sum of angles at $`b_{13}`$ and at $`b_{17}`$ does not change significantly.

Again, the “key” contains the $`n`$ segments $`s_{19},\mathrm{},s_{19+n}`$ of integral lengths $`a_1,\mathrm{},a_n`$ that encode an instance of Partition. As before, let $`S`$ denote the set of integers for the Partition instance. We also use “long” auxiliary segments of lengths $`L/2`$ and $`L`$, where $`L_ia_i=A`$. Here segments $`s_{19}`$ and $`s_{20+n}`$ have length $`L/2`$, while $`s_{21+n}`$ has length $`L`$.

The critical dimensions of the frame are chosen such that the key can just be removed from the frame if and only if it can be collapsed to a length of $`L`$. Removing the key consists in pulling it through the narrow bottleneck formed by the segments $`s_3`$ and $`s_9`$ by extending the “spring” formed by $`s_{14}`$ and $`s_{15}`$, while moving the “keyholder” $`s_{18}`$ down by a distance of $`L+\epsilon `$. This is possible if and only if there is a feasible partition.

More precisely, let the angle at $`b_{17}`$ be $`\psi \pi `$. Let $`\epsilon =O(1/nL)`$. We assume that the dimensions of the frame are chosen sufficiently large to guarantee that moving $`b_{17}`$ down by a vertical distance of $`L+\epsilon `$ increases its distance from $`b_{13}`$ by $`L\mathrm{cos}\psi +\mathrm{\Theta }(\epsilon )`$, i.e., the angles at $`b_{17}`$ and at $`b_{13}`$ do not change much. The segments $`s_{14}`$ and $`s_{15}`$ forming the spring have length $`L/2\mathrm{cos}\psi +\mathrm{\Theta }(\epsilon )`$, so extending the spring will just suffice to move the keyholder $`s_{18}`$ down by $`L+\epsilon `$, but not more. The vertical “height” of the bottleneck, i.e., the length of the segments $`s_3`$ and $`s_9`$, is $`\epsilon /3`$, while the horizontal “width” $`x_8x_3=x_9x_2=\epsilon ^4`$ is significantly smaller. (As we will discuss below, this forces the keyholder to be roughly vertical throughout the motion.) For the initial position of the key inside of the frame, we assume $`L<y_{18}y_3<L+\epsilon /3`$ and $`L<y_{20+n}y_3<L+\epsilon /3`$. Finally, $`y_6y_7=L+\mathrm{\Theta }(\epsilon )`$ and $`x_6x_5=\mathrm{\Theta }(A)`$, so the dimensions of the rectangle formed by $`b_4,b_5,b_6,b_7`$ are not large enough to change the basically vertical orientation of the location segments $`s_{19}`$, $`s_{19+n}`$, and $`s_{20+n}`$.

Now assume that there is a feasible partition, $`S=S_1\stackrel{}{}S_2`$, such that $`_{iS_1}a_i=_{iS_2}a_i`$. By performing a (finite) “wiggly” sequence of moves, we can move the partition segments such that (1) any segment $`s_{19+i}`$ representing $`a_iS_1`$ satisfies $`y_iy_{i1}=a_i+O(\epsilon ^5)`$ and $`|x_ix_{i1}|=O(\epsilon ^5)`$, so that $`s_{19+i}`$ is pointing up; (2) any segment $`s_{19+i}`$ representing $`a_iS_2`$ satisfies $`y_{i1}y_i=a_i+O(\epsilon ^5)`$ and $`|x_ix_{i1}|=O(\epsilon ^5)`$, so that $`s_{19+i}`$ is pointing down; and (3) we end up placing $`b_{20+n}`$ within Euclidean distance $`O(\epsilon ^4)`$ from $`b_{18}`$ and placing $`b_{21+n}`$ at distance $`\epsilon /3+O(\epsilon ^5)`$ from $`b_3`$ and $`b_8`$. Thus, extending the spring by an appropriate wiggly motion moves the key through the bottleneck. Now it is easy to open the joint $`b_{13}`$, and unfold the whole chain.

Conversely, assume that the chain can be unfolded. As discussed above, the sum of angles at $`b_{13}`$ and at $`b_{17}`$ has to change significantly before the frame ceases to be rigid. Now note that the dimensions of the bottleneck force the keyholder segment to be roughly vertical, i.e., to have slope within $`O(1/\epsilon ^3)`$ of vertical. (See Figure 8.) Furthermore, we noted above that any feasible vertical motion of $`b_{17}`$ does not change the angle at $`b_{17}`$ by a significant amount; it is clear that this also prevents the angle at $`b_{13}`$ from changing much. Therefore, the frame remains rigid until the key has been removed from the lock.

Now consider the positions of segments $`s_{18}`$ and $`s_{21+n}`$ when $`b_{21+n}`$ crosses the horizontal line $`y=y_2`$. By the dimensions of the bottleneck, $`s_{21+n}`$ must have a slope within $`\mathrm{\Omega }(1/\epsilon ^3)`$ of vertical. Furthermore, by construction of the rectangle $`b_4b_5b_6b_7`$, we are assured that $`y_{18}y_{20+n}O(\epsilon )`$, i.e., $`s_{20+n}`$ cannot be significantly below $`s_{18}`$. On the other hand, $`b_{20+4n}`$ must be below the horizontal line $`y=y_3`$ when $`b_{18}`$ has been moved down by a vertical distance of $`L+\epsilon `$. Since no segment within the key can change its vertical slope significantly while $`s_{21+n}`$ is within the bottleneck (they must all remain wedged between $`s_{18}`$ and $`s_{21+n}`$ and be strictly contained in the shaded region in Figure 8), we conclude that $`y_{20+n}y_{18}O(\epsilon )`$ upon leaving the bottleneck, i.e., $`s_{20+n}`$ cannot be significantly above $`s_{18}`$.

Therefore, the sets $`S_1=\{i1,\mathrm{},n|y_iy_{i1}\}`$ and $`S_2=\{i1,\mathrm{},n|y_i<y_{i1}\}`$ upon entering the bottleneck from above and leaving it from below must satisfy $`_{iS_1}a_i=_{iS_2}a_i+\mathrm{\Theta }(\epsilon )`$. Since $`ϵ1`$, this implies that there is a feasible partition. $`\mathrm{}`$

For the case of monotonic bend operations, the above proof can be easily modified:

###### Corollary 3.5

It is NP-hard to decide if a polygonal chain $`P`$ with a single vertex-to-vertex incidence can be straightened by monotonic partial single-joint bends.

Proof: The joints in the construction shown in Figure 7 that may not be changed monotonically are $`b_{14},\mathrm{},b_{20+n}`$, the ones that are not part of the frame. By using small quadruple joint gadgets as in the construction for Theorem 3.1, we get a chain that can be opened with monotonic moves, if and only if it can be opened. $`\mathrm{}`$

## 4 Algorithms

In this section, we turn our attention to positive algorithmic results, giving efficient algorithms for deciding if particular bend sequences are feasible. We consider here only the case of complete bends.

Consider an arbitrary permutation, $`\sigma =(i_1,\mathrm{},i_n)`$, of the bends along a wire. In order for $`\sigma `$ to be a foldable sequence, it is necessary and sufficient that for each $`j=1,\mathrm{},n`$ the bend $`b_{i_j}`$ is foldable. Recall that in our notation $`P(\{i_1,\mathrm{},i_{j1}\})`$ denotes the partially bent chain after the bends at $`b_{i_1},\mathrm{},b_{i_{j1}}`$ have been straightened. The point $`b_{i_j}`$ splits $`P(\{i_1,\mathrm{},i_{j1}\})`$ into two subchains; let $`P_0`$ (resp., $`P_{n+1}`$) denote the subchain containing the endpoint $`b_0`$ (resp., $`b_{n+1}`$). Now, $`b_{i_j}`$ is foldable if the joint at $`b_{i_j}`$ can be straightened without causing a collision to occur between $`P_0`$ and $`P_{n+1}`$ at any time during the rotation about $`b_{i_j}`$. We can assume, without loss of generality, that $`P_0`$ is fixed and that $`P_{n+1}`$ is pivoted about $`b_{i_j}`$. During this bend operation at $`b_{i_j}`$, each point, $`u`$, on $`P_{n+1}`$ moves along a circular arc, $`A_u`$, subtending an angle $`\theta _{i_j}`$, centered on $`b_{i_j}`$. It is clear that in order for the bend to be feasible, none of these arcs $`A_u`$ may cross the chain $`P_0`$, for all choices of points $`u`$ on $`P_{n+1}`$.

If the perpendicular projection of $`b_{i_j}`$ onto the line containing an edge $`e`$ of $`P_{n+1}`$ lies on the edge, let $`w_ee`$ denote the projection point. (Each edge of $`P_{n+1}`$ has at most one projection point.) Let $`U`$ denote the union of the set of vertices of $`P_{n+1}`$ and the set of projection points on edges of $`P_{n+1}`$. In the lemma below, we observe that, in order to test feasibility of straightening the bend $`b_{i_j}`$, it suffices to consider only the feasibility of the final position of the chain $`P_{n+1}`$ and to test $`P_0`$ for intersection with the discrete set $`𝒜=\{A_u:uU\}`$. See Figure 9.

###### Lemma 4.1

Joint $`b_{i_j}`$ is foldable if and only if (1) no arc of $`𝒜`$ intersects $`P_0`$, and (2) after the bend, no segment of $`P_{n+1}`$ intersects a segment of $`P_0`$.

Proof: If joint $`b_{i_j}`$ is foldable then, by definition, there can be no intersection of $`P_{n+1}`$ with $`P_0`$ during its rotation about $`b_{i_j}`$. This implies conditions (1) and (2).

If conditions (1) and (2) hold, then we claim that there can be no intersection of $`P_{n+1}`$ with $`P_0`$ during the rotation. Consider a subsegment, $`s`$, of $`P_{n+1}`$ whose endpoints are consecutive points of $`U`$. (Note that at least one endpoint of $`s`$ must be a vertex of $`P_{n+1}`$.) During the rotation, it sweeps a region $`R_s`$ that is bounded by two circular arcs centered at $`b_{i_j}`$, corresponding to the trajectories of its endpoints during the rotation, and two line segments, corresponding to the positions of $`s`$ before and after the rotation. Here, we are using the fact that the distance from $`b_{i_j}`$ to a point $`qs`$ monotonically changes as a function of the position of $`q`$ on $`s`$. (The projection points were introduced in order to assure this property.) Our claim follows from the fact that $`P_0`$ is a simple, connected chain: It cannot intersect $`s`$ at some intermediate stage of the rotation unless it intersects the boundary of the region $`R_s`$. Such an intersection is exactly what is being checked with conditions (1) and (2). $`\mathrm{}`$

###### Lemma 4.2

For any $`SB`$, and any $`b_iS`$, one can decide in $`O(n\mathrm{log}n)`$ time if joint $`b_i`$ is foldable for the chain $`P(S)`$.

Proof: Using standard plane sweep methods for segment intersections, adapted to include circular arcs, we can check in $`O(n\mathrm{log}n)`$ time both conditions ((1) and (2)) of Lemma 4.1. Events in the sweep algorithm correspond to joints and to vertical points of tangency of circular arcs, assuming we use a vertical sweep line. During the sweep, we keep track of the vertical ordering of the segments and arcs that cross the sweep line; we check for intersection between any two objects that become adjacent in this ordering, stopping if a crossing is detected. Since we process $`O(n)`$ events, each at a cost of $`O(\mathrm{log}n)`$, the time bound follows. $`\mathrm{}`$

###### Remark 4.3

Condition (2) can be tested in linear time, by Chazelle’s triangulation algorithm. We suspect that condition (1) can also be tested in linear time. Condition (1) involves testing for rotational separability of two simple chains about a fixed center point ($`b_i`$), which is essentially a polar coordinate variant of translational separability (which is easily tested for simple chains using linear-time visibility (lower envelope) calculation). The issue that must be addressed for our problem, though, is the “wrap-around” effect of the rotation; we believe that this can be resolved and that this idea should lead to a reduction in running time of a factor of $`\mathrm{log}n`$.

###### Corollary 4.4

The foldability of a permutation $`\sigma `$ can be tested in $`O(n^2\mathrm{log}n)`$ time.

We obtain improved time bounds for testing the feasibility of a particularly important folding sequence: the identity permutation. Many real tube-bending and wire-bending machines operate in this way, making bends sequentially along the wire/tube. (Such is the case for the hydraulic tube-bending machines at Boeing’s factory, where this problem was first suggested to us.) Of course, there are chains $`P`$ that can be straightened using an appropriate folding sequence but cannot be straightened using an identity permutation folding sequence; see Figure 1(e). However, for this special case of identity permutations, we obtain an algorithm for determining feasibility that runs in nearly linear time:

###### Theorem 4.5

In time $`O(n\mathrm{log}^2n)`$ one can verify if the identity permutation ($`\sigma =(1,2,\mathrm{},n)`$) is a foldable permutation for $`P`$.

Proof: For notational convenience, we consider the equivalent problem of verifying if it is feasible, in the order $`b_1,b_2,\mathrm{},b_n`$, to bend the joints $`b_i`$ from joint angle $`\pi `$ to final angle $`\theta _i`$, thereby transforming a straight wire into the final shape $`P`$, rather than our convention until now of considering the problem of performing bend operations to straighten the chain $`P`$.

Thus, consider performing the bends in the order given by the identity permutation $`\sigma `$, and consider the moment when we are testing the foldability of $`b_i`$. The subchain $`P_{n+1}`$, from $`b_i`$ to $`b_{n+1}`$, is a single line segment, $`b_ib_{n+1}`$, since the joints $`b_{i+1},\mathrm{},b_n`$ are straight at the moment. Thus, verifying the foldability of bend $`b_i`$ amounts to testing if the segment $`b_ib_{n+1}`$ can be rotated about $`b_i`$ by the desired amount, without colliding with any other parts of the subchain $`P_0`$ of $`P`$, from $`b_0`$ to $`b_i`$. In other words, we must do a wedge emptiness query with respect to $`P_0`$, defined by $`b_i`$, segment $`b_ib_{n+1}`$, and the angle $`\theta _i`$. Since $`P_0`$ is connected, emptiness can be tested by verifying that the boundary of the wedge does not intersect $`P_0`$. (See Figure 10.) Thus, we can perform this query by using (straight) ray shooting and circular-arc ray shooting in $`P_0`$; the important issue is that $`P_0`$ is dynamically changing as we proceed with more bends.

However, in order to avoid the development of potentially complex dynamic circular-arc ray shooting data structures, we devise a simple and efficient method that “walks” along portions of $`P_0`$, testing for intersection with the circular arc, $`\gamma `$, from $`b_{n+1}`$ to $`b_{n+1}^{}`$, where $`b_{n+1}^{}`$ is the location of $`b_{n+1}`$ after the bend at $`b_i`$ has been performed.

In particular, we keep track of a “painted” portion of $`P_0`$, which corresponds to the subset of $`P_0`$ that has been “walked over.” We consider the chain $`P_0`$ to be a degenerate simple polygon, having two sides which form a counterclockwise loop around $`P_0`$. We consider the case in which the bend at $`b_i`$ is a rotation of the segment $`b_ib_{n+1}`$ clockwise to the segment $`b_ib_{n+1}^{}`$; the case of a counterclockwise bend at $`b_i`$ is handled similarly. When we perform a bend at $`b_i`$, we walk (counterclockwise) along the unpainted portions of $`P_0`$, between two points, $`a`$ and $`a^{}`$, on the boundary of $`P_0`$, where $`a`$ and $`a^{}`$ are defined according to cases that depend on the outcomes of two ray-shooting queries:

If both of the rays $`\stackrel{}{b_ib_{n+1}}`$ and $`\stackrel{}{b_ib_{n+1}^{}}`$ miss $`P_0`$ (and go off to infinity), then there is nothing more to check: the rotation at $`b_i`$ can be done without interference with $`P_0`$, since $`P_0`$ is a (connected) polygonal chain lying in the complement of the wedge defined by $`\stackrel{}{b_ib_{n+1}}`$ and $`\stackrel{}{b_ib_{n+1}^{}}`$. See Figure 11.

If both of the rays $`\stackrel{}{b_ib_{n+1}}`$ and $`\stackrel{}{b_ib_{n+1}^{}}`$ hit $`P_0`$, then we let $`a`$ and $`a^{}`$ (respectively) be the points on the boundary of $`P_0`$ where they first hit $`P_0`$. See Figure 12.

If exactly one of the rays $`\stackrel{}{b_ib_{n+1}}`$ and $`\stackrel{}{b_ib_{n+1}^{}}`$ hits $`P_0`$ while the other misses $`P_0`$ (and goes off to infinity), then we define $`a`$ and $`a^{}`$ as follows. Assume that the ray $`\stackrel{}{b_ib_{n+1}}`$ hits $`P_0`$ (and the ray $`\stackrel{}{b_ib_{n+1}^{}}`$ misses $`P_0`$); the other case is handled similarly (see Figure 13, right). Then, we define $`a`$ to be the point on the boundary of $`P_0`$ where the ray $`\stackrel{}{b_ib_{n+1}}`$ hits $`P_0`$, and we define $`a^{}`$ to be the point on the boundary of $`P_0`$ where a ray from infinity in the direction $`\stackrel{}{b_{n+1}b_i}`$ (towards $`b_i`$) hits $`P_0`$. See Figure 13, left.

During the walk from $`a`$ to $`a^{}`$ along the boundary of $`P_0`$, we test each segment for intersection with the circular arc $`\gamma `$ in time $`O(1)`$. Whenever we reach a portion of the boundary that is already painted, we skip over that portion, going immediately to its end. Already painted portions have endpoints that were determined by rays in previous steps of the painting procedure. Since there are only a total of $`O(n)`$ rays (one per edge of $`P`$), this implies only $`O(n)`$ endpoints of painted portions. As we walk, we mark the corresponding portions over which we walk as “painted.” Since, by continuity, it is easy to see that the painted portion of any one segment of $`P_0`$ is connected, we know that we must encounter at least one vertex of $`P_0`$ between the time that the walk leaves a painted portion and the time that the walk enters the next painted portion. Thus, during a walk, we charge the tests that we do for intersection with $`\gamma `$ off to the vertices that are being painted. The remainder of the justification of the algorithm is based on two simple claims:

###### Claim 4.6

There is no need to walk back over a painted portion in order to check for intersections with an arc $`\gamma `$ at some later stage.

Proof: The fact that we need not walk over a painted portion testing again for intersections with $`\gamma `$ follows from the fact that with each bend in the sequence, the length of the segment $`b_ib_{n+1}`$ that we are rotating goes down by the length of the last link. Thus, if the motion of the tip, $`b_{n+1}`$, sweeps an arc $`\gamma `$ that does not reach a portion $`\mu `$ of the boundary of $`P_0`$ when the link $`b_ib_{n+1}`$ is straight, it cannot later be that a link $`b_jb_{n+1}`$ ($`j>i`$) can permit the tip $`b_{n+1}`$ to reach the same portion $`\mu `$ when pivoting is done about $`b_j`$; this is a consequence of the triangle inequality. $`\mathrm{}`$

###### Claim 4.7

In testing for intersection with $`\gamma `$, we check enough of the chain $`P_0`$: if any part of it intersects $`\gamma `$, then it must lie on the portion between $`a`$ and $`a^{}`$ over which we walk.

Proof: In case (a), there is nothing to check. In case (b), the closed Jordan curve from $`b_i`$ to $`a`$ (along a straight segment), then along the boundary of the simple polygon $`P_0`$ to $`a^{}`$, then back to $`b_i`$ (along a straight segment) forms the boundary of a region whose only intersection with $`P_0`$ is along the shared boundary from $`a`$ to $`a^{}`$; thus, if $`\gamma `$ lies within this region (i.e., does not intersect the boundary of $`P_0`$ from $`a`$ to $`a^{}`$), then $`\gamma `$ does not intersect any other portion of $`P_0`$. In case (c) we argue similarly, but we use the Jordan region defined by the segment from $`b_i`$ to $`a`$, the boundary of $`P_0`$ from $`a`$ to $`a^{}`$, the ray from $`a^{}`$ to infinity (in the direction of $`\stackrel{}{b_ib_{n+1}}`$), then the reverse of the ray $`\stackrel{}{b_ib_{n+1}^{}}`$ back to $`b_i`$. $`\mathrm{}`$

The total time for walking along the chain $`P_0`$ can be charged off to the vertices of $`P`$, resulting in time $`O(n)`$ for tests of intersection with arcs $`\gamma `$, exclusive of the ray shooting time. The final time bound is then dominated by the time to perform $`n`$ straight ray shooting queries in a dynamic data structure for the changing polygonal chain $`P_0`$; these ray shooting queries are utilized both in testing for intersection with the segment $`b_ib_{n+1}^{}`$ and in determining the points $`a`$ and $`a^{}`$ that define the walk. These ray-shooting queries and updates are done in time $`O(\mathrm{log}^2n)`$ each, using existing techniques (), leading to the claimed overall time bound. $`\mathrm{}`$

Next, we turn to two other important classes of permutations. Again, for notational convenience, we consider the problem of verifying if it is feasible, in the order given by the permutation, to bend the joints $`b_i`$ from joint angle $`\pi `$ to final angle $`\theta _i`$, thereby transforming a straight wire into the final shape $`P`$. We say that a permutation is an outwards folding sequence (resp., inwards folding sequence) if at any stage of the folding, the set of bends that have been completed, and therefore are not straight, is a subinterval, $`b_i,b_{i+1},\mathrm{},b_j`$ (resp., a pair of intervals $`b_1,b_2,\mathrm{},b_i`$ and $`b_j,b_{j+1},\mathrm{},b_n`$); thus, the next bend to be performed is either $`b_{i1}`$ or $`b_{j+1}`$ (resp., $`b_{i+1}`$ or $`b_{j1}`$). Inwards and outwards folding sequences are a subclass of permutations that model a constraint imposed by some forming machines. See Figure 14. The identity permutation is a folding sequence that is a special case of both an inwards and an outwards folding sequence.

We show that one can efficiently search for a folding sequence that is inwards or outwards. Our algorithms are based on dynamic programming.

First, consider the case of outwards folding sequences. We keep track of the state as the pair $`(i,j)`$ representing the interval of bends ($`b_i,b_{i+1},\mathrm{},b_j`$) already completed. We construct a graph $`𝒢`$ whose $`O(n^2)`$ nodes are the states $`(i,j)`$ (with $`1i<jn`$) and whose edges link states that correspond to the action of completing a bend at $`b_{i1}`$ or $`b_{j+1}`$ (if the starting state is $`(i,j)`$). Thus, each node has constant degree. Our goal is to determine if there is a path in this graph from some $`(i,i)`$, for $`i\{1,2,\mathrm{},n\}`$ to $`(1,n)`$. We augment this graph with a special node $`\nu _0`$, linked to each node $`(i,i)`$. Then, our problem is readily solved in $`O(n^2)`$ time once we have the graph constructed, since it is simply searching for a path from node $`\nu _0`$ to node $`(1,n)`$. (Alternatively, we can construct the graph as we search the graph for a path.) In order to construct the graph, we need to test whether bend $`b_{i1}`$ or $`b_{j+1}`$ can be performed without intersecting the folded chain, $`P^{}`$, linking $`b_{i1}`$ to $`b_{j+1}`$. This is done in a manner very similar to that we described above for the case of identity permutations: we perform ray-shooting queries in time $`O(\mathrm{log}^2n)`$ and then use a “painting” procedure to keep track of the states of $`2n2`$ “walks” that determine circular-arc ray shooting queries. In particular, there is a separate painting procedure corresponding to each of the $`n1`$ choices of $`i`$ and to each of the $`n1`$ choices of $`j`$. For example, for a fixed choice of $`i`$, the painting procedure will consider each of the possible bends $`b_{i+1},\mathrm{},b_n`$ in order, allowing us to amortize the cost of checking for intersections with the circular arc $`\gamma `$ associated with each bend. In total, the cost of the walks is $`O(n^2)`$, while there may also be $`O(n^2)`$ ray shooting queries (in a dynamically changing polygon). Thus, the total cost is dominated by the ray shooting queries, giving an overall time bound of $`O(n^2\mathrm{log}n)`$.

For the case of an inwards folding sequence, we build a similar state graph and search it. However, the cost of testing if a bend is feasible is somewhat higher, as we do not have an especially efficient procedure for testing the foldability of a polygonal chain. (Our painting procedures exploit the fact that the link being folded is straight.) Thus, we apply the relatively naive method of testing feasibility given in Lemma 4.2, at a cost of $`O(n\mathrm{log}n)`$ per test (which potentially improves to $`O(n)`$ time, if our conjecture mentioned in the remark after the Lemma is true). Thus, the overall cost of the algorithm is dominated by the $`O(n^2)`$ feasibility tests, at a total cost of $`O(n^3\mathrm{log}n)`$. In summary, we have:

###### Theorem 4.8

In time $`O(n^2\mathrm{log}^2n)`$ one can determine if there is an outwards folding sequence; in time $`O(n^3\mathrm{log}n)`$ one can determine if there is an inwards folding sequence.

## 5 Conclusion

We conclude with some open problems that are suggested by our work:

Is the bend sequencing problem for wire folding strongly NP-complete, or is there a pseudo-polynomial-time algorithm? If not in wire bending, is it strongly NP-complete for the 3-dimensional sheet metal folding problem?

Is it NP-hard to decide if a polygonal chain in three dimensions can be straightened? In  simple examples of locked chains in three dimensions are shown; can these be extended to a hardness proof for the decision problem?

In practice, in order to make a bend using a punch and die on a press brake, it is necessary to consider accessibility constraints. For each bend operation, the die is placed on one side of the material, while the punch is placed on the other side. The bend is formed by pushing the punch into the die (which has a matching shape), with the material in between. (See Wang .) In the simplest model of this operation on a wire, we can consider the punch and the die to be oppositely directed rays that form a bend by coming together (from opposite sides of the wire) so that their apices meet at the bend point. The accessibility constraint in this simple model is that the rays representing the punch and die must be disjoint from the wire structure both at the initial placement of these “tools” and during the bend operation itself.

Can the foldability of a permutation be decided in subquadratic time for wire bending? This would be possible if one had a dynamic data structure that will permit efficient (sublinear) queries for the foldability of a vertex.

### Acknowledgments

We thank an anonymous referee for pointing out some errors in an earlier draft and for many valuable suggestions to improve the presentation. We thank Steve Skiena for valuable input in the early stages of this research and, in particular, for contributing ideas to the hardness proof of Theorem 3.1. We also thank Erik Demaine for discussions leading to the current version of Theorem 3.2. Estie Arkin acknowledges support from the National Science Foundation (CCR-9732221,CCR-0098172) and HRL Laboratories. Sándor Fekete acknowledges support from the National Science Foundation (ECSE-8857642,CCR-9204585) during his time at Stony Brook (1992-93), when this research was initiated. Joe Mitchell acknowledges support from HRL Laboratories, the National Science Foundation (CCR-9732221,CCR-0098172), NASA Ames Research Center, Northrop-Grumman Corporation, Sandia National Labs, Seagull Technology, and Sun Microsystems.


format: text

text:
# Bose-Einstein condensation in dense nuclear matter and strong magnetic fields

## Abstract

Bose-Einstein condensation of antikaons in cold and dense beta-equilibrated matter under the influence of strong magnetic fields is studied within a relativistic mean field model. For magnetic fields $`>5\times 10^{18}`$G, the phase spaces of charged particles are modified resulting in compositional changes in the system. The threshold density of $`K^{}`$ condensation is shifted to higher density compared with the field free case. In the presence of strong fields, the equation of state becomes stiffer than that of the zero field case.

PACS: 03.75.Fi, 26.60.+c, 21.65.+f

Recently, it has been inferred that some soft gamma ray repeaters (SGRs) and perhaps certain anomalous X-ray pulsars (AXPs) could be neutron stars having large magnetic fields $`10^{14}10^{16}`$ G . Those objects are called ”magnetars” . Earlier large magnetic fields $`10^{13}`$G were estimated to be associated with the surfaces of some radio pulsars . The origin of such ultra strong magnetic fields is still an unsolved problem. An attractive idea about the origin is that the small magnetic field of a progenitor star is amplified due to the magnetic flux conservation during the gravitational collapse of the star . Recently, Thomson and Duncan argued that a convective dynamo mechanism might result in large fields $`10^{15}`$G . On the other hand, it is presumed from the scalar virial theorem  based on Newtonian gravity that the limiting interior field in neutron stars could be as large as $`10^{18}`$G . From the general relativistic calculation of axis-symmetric neutron stars in magnetic fields, it follows that neutron stars could sustain magnetic fields $`10^{18}`$G . Because of highly conducting core, such large interior fields may be frozen and could not be directly accessible to observation. Its effects may be manifested in various observables such as the mass-radius relationship, neutrino emissivity etc. Motivated by the existence of large fields in the core of neutron stars, its influence on the gross properties of neutron stars was studied by various groups . The calculations in the relativistic mean field (RMF) approach showed that the equation of state (EoS) was modified due to the Landau quantization and also by the interaction of magnetic moments of baryons with the field . The intense magnetic field was found to change the composition of beta equilibrated matter relevant to neutron stars drastically . The neutrino emissivity in neutron stars was reported to be enhanced in strong magnetic fields .

Besides strong interior fields, many exotic forms of matter may exist in the dense core of neutron stars. One such possibility is the appearance of the Bose-Einstein condensate of strange particles. Nelson and Kaplan first pointed out that antikaons may undergo the Bose-Einstein condensation (BEC) in dense matter at zero temperature because of the attractive s-wave antikaon-nucleon interaction . Later, this idea was applied to neutron stars by various authors . Bose-Einstein condensation in a magnetic field is an old and interesting problem in other branches of physics also namely condensed matter physics and statistical physics. It was shown by Schafroth  that a non-relativistic Bose gas could not condense in an external magnetic field. There are some calculations on the condensation of relativistic charged Bose gas in magnetic fields in the literature . Elmfors and collaborators  noted that the relativistic Bose gas might condense for spatial dimension $`d5`$. They showed that the number density of bosons in the ground state diverges for $`d<5`$ in the presence of a magnetic field. On the other hand, it was argued  that the condensation of bosons in a magnetic field could occur in three dimension if the chemical potential of bosons was taken as a function of density, temperature and magnetic field . In this case, the BEC would be a diffuse one because there is no definite critical temperature. It was also shown in the latter calculation  that the number density of bosons in the ground state was finite. Recently, Suh and Mathews  have studied pion condensation in a beta equilibrated non-interacting n-p-e-$`\mu `$ system in magnetic fields.

In this paper, we investigate the influence of strong magnetic fields on the Bose-Einstein condensation of antikaons in cold and dense matter relevant to neutron stars. This may have profound implications on the gross properties of neutron stars. This method of studying the BEC in strong magnetic fields and dense matter is rather general; therefore it should be of correspondingly broad interest.

We consider strong magnetic field effects on antikaon condensation in the beta equilibrated neutron star matter composed of neutrons, protons, electrons, muons and $`K^{}`$ mesons within the framework of a relativistic field theoretical model . As the constituents in neutron stars are highly degenerate, the chemical potentials of baryons are larger than the temperature of the system. Therefore, the gross properties of neutron stars are calculated at zero temperature. The total Lagrangian density may be written as the sum of baryonic, kaonic and leptonic parts i.e. $`=_B+_K+_l`$. In a uniform magnetic field, the baryonic Lagrangian density  is given by

$`_B`$ $`=`$ $`{\displaystyle \underset{B=n,p}{}}\overline{\psi }_B\left(i\gamma _\mu D^\mu m_B+g_{\sigma B}\sigma g_{\omega B}\gamma _\mu \omega ^\mu g_{\rho B}\gamma _\mu 𝒕_B𝝆^\mu \kappa _B\sigma _{\mu \nu }F^{\mu \nu }\right)\psi _B`$ (3)
$`+{\displaystyle \frac{1}{2}}\left(_\mu \sigma ^\mu \sigma m_\sigma ^2\sigma ^2\right)U(\sigma )`$
$`{\displaystyle \underset{k=\omega ,\rho }{}}\left[{\displaystyle \frac{1}{4}}\left(_\mu V_\nu ^k_\nu V_\mu ^k\right)^2{\displaystyle \frac{1}{2}}m_k^2(V_\mu ^k)^2\right]+{\displaystyle \frac{1}{4}}g_4\left(\omega _\mu \omega ^\mu \right)^2{\displaystyle \frac{1}{4}}F^{\mu \nu }F_{\mu \nu }.`$
Here $`\psi _B`$ denotes the Dirac spinor for baryon B with vacuum mass $`m_B`$ and isospin operator $`𝒕_B`$. The scalar self-interaction term  is, $`U(\sigma )=g_2\sigma ^3/3+g_3\sigma ^4/4`$. Following Ref., the interaction of anomalous magnetic moments of baryons with magnetic fields is given by the last term under the summation in Eq.(1). Here, $`F^{\mu \nu }`$ is the electromagnetic field tensor, $`\sigma _{\mu \nu }=[\gamma _\mu ,\gamma _\nu ]/2`$ and $`\kappa _B`$ is the experimentally measured value of magnetic moment for baryon $`B`$. The covariant derivative for a charged particle is $`D^\mu =^\mu +iqA^\mu `$ with the choice of gauge corresponding to the constant magnetic field ($`B_m`$) along z-axis is $`A_0=0`$, $`𝐀(0,xB_m,0)`$. The form of 4-component spinor solutions for baryons is given by Ref. . The (anti)kaon-nucleon interaction is treated in the same footing as that of the nucleon-nucleon interaction . Therefore, the kaonic Lagrangian density in a magnetic field is given as,

$$_K=D_\mu ^{}K^{}D^\mu Km_K^2K^{}K,$$
(4)
where the covariant derivative $`D_\mu =_\mu +iqA_\mu +ig_{\omega K}\omega _\mu +ig_{\rho K}𝒕_K𝝆_\mu `$. There is no interaction term involving magnetic moments in the kaonic Lagrangian density because (anti)kaons having zero spin angular momentum do not possess magnetic moments. The effective mass of (anti)kaons in this minimal coupling scheme is given by $`m_K^{}=m_Kg_{\sigma K}\sigma `$. The solution for negatively charged kaons in a magnetic field is $`K\left(qB_m/\pi \right)^{1/4}(1/\sqrt{2^nn!})\mathrm{e}^{i\omega _K^{}t+ip_yy+ip_zz}\mathrm{e}^{qB_m\eta ^2/2}H_n(\sqrt{qB_m}\eta )`$, where $`\eta =x+p_y/qB_m`$, ”H” denotes the Hermite polynomial with $`n`$ the Landau principal quantum number. The Lagrangian density for neutrons is obtained by putting $`q=0`$ in the covariant derivatives of Eq. (1). In the mean field approximation , the meson field equations in the presence of antikaon condensate and magnetic field are

$`m_\sigma ^2\sigma `$ $`=`$ $`{\displaystyle \frac{U}{\sigma }}+{\displaystyle \underset{B}{}}g_{\sigma B}n_B^S+g_{\sigma K}{\displaystyle \frac{m_K^{}}{\sqrt{m_K^2+qB_m}}}n_K^{},`$ (5)
$`m_\omega ^2\omega _0+g_4\omega _0^3`$ $`=`$ $`{\displaystyle \underset{B}{}}g_{\omega B}n_Bg_{\omega K}n_K^{},`$ (6)
$`m_\rho ^2\rho _{03}`$ $`=`$ $`{\displaystyle \underset{B}{}}g_{\rho B}I_{3B}n_B+g_{\rho K}I_{3K^{}}n_K^{}.`$ (7)
where $`n_B`$ and $`n_B^s`$ are baryon and scalar density for baryon B respectively; $`I_{3B}=+1/2`$ for protons, $`1/2`$ for neutrons and $`I_{3K^{}}=1/2`$ for $`K^{}`$ mesons. The expressions of the scalar and baryon density corresponding to protons are given by

$`n_p^s`$ $`=`$ $`{\displaystyle \frac{|q_p|B_m}{2\pi ^2}}{\displaystyle \underset{\nu }{}}{\displaystyle \underset{s}{}}m_p^{}{\displaystyle \frac{\overline{m_p}}{\overline{m_p}s\kappa _pB_m}}\mathrm{ln}\left(\left|{\displaystyle \frac{E_f^p+k_{f,\nu ,s}^p}{\overline{m_p}}}\right|\right),`$ (8)
and

$$n_p=\frac{|q_p|B_m}{2\pi ^2}\underset{\nu }{}\underset{s}{}k_{f,\nu ,s}^p,$$
(9)
where the energy spectrum for protons is given by

$`E_{p,\nu ,s}`$ $`=`$ $`\sqrt{k_z^2+\left(\sqrt{m_p^2+2\nu q_pB_m}+s\kappa _pB_m\right)^2}+g_{\omega _p}\omega _0+{\displaystyle \frac{1}{2}}g_{\rho _p}\rho _{03},`$ (10)
$$\overline{m_p}=\sqrt{m_p^2+2\nu q_pB_m}+s\kappa _pB_m,$$
(11)
and

$$k_{f,\nu ,s}^p=\sqrt{E_f^{p2}\left(\sqrt{m_p^2+2\nu q_pB_m}+s\kappa _pB_m\right)^2}.$$
(12)
Similarly for neutrons, those expressions are given by

$$n_n^s=\frac{m_n^{}}{4\pi ^2}\underset{s}{}k_{f,s}E_f^n\overline{m}^2\mathrm{ln}\left(\left|\frac{E_f^n+k_{f,s}}{\overline{m}}\right|\right),$$
(13)
and

$$n_n=\frac{1}{2\pi ^2}\underset{s}{}\frac{1}{3}k_{f,s}^3+\frac{1}{2}s\kappa _nB_m\left[\overline{m}k_{f,s}+E_f^{n2}\left(\mathrm{arcsin}\frac{\overline{m}}{E_f^n}\frac{\pi }{2}\right)\right],$$
(14)
where

$$E_{n,s}=\sqrt{k_z^2+\left(\sqrt{m_n^2+k_x^2+k_y^2}+s\kappa _nB_m\right)^2}+g_{\omega _n}\omega _0\frac{1}{2}g_{\rho _n}\rho _{03},$$
(15)
$$\overline{m}=m_n^{}+s\kappa _nB_m,$$
(16)
and

$$k_{f,s}=\sqrt{E_f^{n2}\overline{m}^2}.$$
(17)
Solving the equation of motion for antikaons, the in-medium energy of $`K^{}`$ meson in a magnetic field is obtained as $`\omega _K^{}=\sqrt{p_z^2+m_K^2+qB_m(2n+1)}g_{\omega K}\omega _0g_{\rho K}\rho _{03}/2`$. The condition for the condensation of $`K^{}`$ meson in a magnetic field is $`p_z=0`$ and $`n=0`$. The number density of $`K^{}`$ meson in a magnetic field and in the ground state is obtained from the relation $`J_\mu ^K=i(K^{}/^\mu K^{}/^\mu KK)`$ and it is given by, $`n_K^{}=J_0^K^{}=2(\omega _K^{}+g_{\omega K}\omega _0+g_{\rho K}\rho _{03}/2)K^{}K`$. The total energy density is given by

$`\epsilon `$ $`=`$ $`{\displaystyle \frac{1}{2}}m_\sigma ^2\sigma ^2+{\displaystyle \frac{1}{3}}g_2\sigma ^3+{\displaystyle \frac{1}{4}}g_3\sigma ^4+{\displaystyle \frac{1}{2}}m_\omega ^2\omega _0^2+{\displaystyle \frac{3}{4}}g_4\omega _0^4+{\displaystyle \frac{1}{2}}m_\rho ^2\rho _{03}^2`$ (19)
$`+{\displaystyle \underset{B=n,p}{}}\epsilon _B+{\displaystyle \underset{l}{}}\epsilon _l+\epsilon _{\overline{K}},`$
where $`\epsilon _B`$ and $`\epsilon _l`$ correspond to the kinetic energy densities of baryons and leptons respectively. The kinetic energy densities of protons and neutrons in a magnetic field are given by

$$\epsilon _p=\frac{|q_p|B_m}{4\pi ^2}\underset{\nu }{}\underset{s}{}E_f^pk_{f,\nu ,s}^p+\overline{m_p}^2\mathrm{ln}\left(\left|\frac{E_f^p+k_{f,\nu ,s}^p}{\overline{m_p}}\right|\right),$$
(20)
and

$`\epsilon _n`$ $`=`$ $`{\displaystyle \frac{1}{4\pi ^2}}{\displaystyle \underset{s}{}}{\displaystyle \frac{1}{2}}E_f^{n3}k_{f,s}+{\displaystyle \frac{2}{3}}s\kappa _nB_mE_f^{n3}\left(\mathrm{arcsin}{\displaystyle \frac{\overline{m}}{E_f^n}}{\displaystyle \frac{\pi }{2}}\right)`$ (21)
$`+`$ $`\left({\displaystyle \frac{1}{3}}s\kappa _nB_m{\displaystyle \frac{1}{4}}\overline{m}\right)\left[\overline{m}k_{f,s}E_f^n+\overline{m}^3\mathrm{ln}\left(\left|{\displaystyle \frac{E_f^n+k_{f,s}}{\overline{m}}}\right|\right)\right].`$ (22)
Similarly, the expression for the kinetic energy density of electrons has the same form as that of protons but electrons are noninteracting and anomalous magnetic moment of electrons is not considered here . The energy density for antikaons in the condensate state is $`\epsilon _{\overline{K}}=\sqrt{m_K^2+qB_m}n_K^{}`$. The other terms in Eq. (16) represent interaction energy densities. The pressure of the system follows from the relation $`P=\mu _nn_b\epsilon `$, where $`\mu _n`$ and $`n_b`$ are the neutron chemical potential and total baryon density, respectively. In the core of neutron stars, strangeness changing processes such as $`np+K^{}`$ and $`e^{}K^{}+\nu _e`$ occur. The chemical equilibrium yields $`\mu _n\mu _p=\mu _K^{}=\mu _e`$, where $`\mu _p`$ and $`\mu _K^{}`$ are respectively the chemical potentials of protons and $`K^{}`$ mesons. Employing Eq. (3) in conjunction with the chemical equilibrium conditions and charge neutrality $`n_pn_K^{}n_en_\mu =0`$, we obtain the effective masses self-consistently.

In the effective field theoretical approach adopted here, two different sets of coupling constants for nucleons and kaons with $`\sigma `$, $`\omega `$ and $`\rho `$ meson are required. The nucleon-meson coupling constants are obtained by fitting experimental data for binding energies and charge radii for heavy nuclei . This set of parameters is known as TM1 set. The values of coupling constants are $`g_{\sigma N}=10.0289`$, $`g_{\omega N}=12.6139`$, $`g_{\rho N}=4.6322`$, $`g_2=7.2325fm^1`$, $`g_3=0.6183`$ and $`g_4=71.3075`$. The incompressibility of matter at normal nuclear matter density ($`n_0=0.145fm^3`$) is 281 MeV for the TM1 model. According to the simple quark model and isospin counting rule, the kaon-vector meson coupling constants are $`g_{\omega K}=\frac{1}{3}g_{\omega N}`$ and $`g_{\rho K}=g_{\rho N}`$. On the other hand, the scalar coupling constant is obtained from the real part of the antikaon optical potential at normal nuclear matter density i.e. $`U_{\overline{K}}(n_0)=g_{\sigma K}\sigma g_{\omega K}\omega _0`$ . In this calculation, we have taken $`U_{\overline{K}}(n_0)=160`$ MeV and the scalar coupling is $`g_{\sigma K}=2.0098`$.

The TM1 model was adopted earlier for the description of heavy nuclei and the equation of state for neutron stars . Besides the non-linear $`\sigma `$ meson terms, the model also includes non-linear $`\omega `$ meson term. It was shown  that the TM1 model reproduced scalar and vector potentials close to those of the relativistic Brueckner Hartree Fock calculation using the realistic nucleon-nucleon interaction . Recently, the TM1 model was used for the investigation of antikaon condensation in neutron star matter  for zero field. For TM1 parameter set, it was found that the phase transition was of second order . In the TM1 model, the maximum masses and central densities of neutron stars without and with antikaon condensation where $`U_K^{}=160`$ MeV are respectively, 2.179(1.857)$`M_{}`$ and 5.97(6.37)$`n_0`$.

In Figure 1, number densities of various particles are plotted with baryon density. The particle densities for $`B_m=0`$ are shown by the solid lines, whereas those corresponding to $`B_m=1.5\times 10^5B_c^e`$ are denoted by the dashed lines. The critical field for electrons ($`B_c^e`$) is that value where cyclotron quantum is equal to or above the rest energy of an electron and its value is $`B_c^e=4.414\times 10^{13}`$G. Here we note that the formation of $`K^{}`$ condensation is delayed to higher density than the field free case. The threshold densities of $`K^{}`$ condensation corresponding to $`B_m=0`$ and $`B_m=1.5\times 10^5B_c^e`$ are 2.67$`n_0`$ and 3.85$`n_0`$ respectively. The delayed appearance of $`K^{}`$ condensation may be attributed to the stiffer EoS because of the effects of magnetic moments. In the presence of the field, the enhancement of electron and muon fraction are pronounced whereas the proton fraction is smaller than the zero field value beyond 2.7$`n_0`$. With the appearance of $`K^{}`$ condensate, it would try to diminish electron and muon density. On the other hand, the phase spaces of electrons and muons are so strongly modified in a quantizing field that their fractions are significantly increased. The net result is the reduction in the density of $`K^{}`$ condensate than that of the field free case. The proton density increases after the onset of $`K^{}`$ condensation. The neutron fraction also increases because of the interaction of anomalous magnetic moment of neutrons with the field. This may have important effects on the equation of state.

In the presence of magnetic fields $`>5\times 10^{18}`$G, the nucleon effective mass is enhanced in the high density regime than that of the field free case. This may be attributed to the effects of magnetic moments as it was also noted in Ref.. The (anti)kaon effective mass in magnetic fields does not change appreciably from the zero field case.

The onset of $`K^{}`$ condensation is given by the equality of $`K^{}`$ chemical potential ($`\mu _K^{}`$) with electron chemical potential ($`\mu _e`$). In the presence of magnetic field, we find the hadronic phase smoothly connects to the antikaon condensate phase resulting in a second order phase transition as it is evident from equation of state (pressure versus energy density curve) in Figure 2. For TM1 parameter set, we note that the phase transition is of second order with and without magnetic field.

In Figure 2, matter pressure ($`P`$) versus matter energy density ($`ϵ`$) is displayed for $`B_m=0`$ (curve I), $`B_m=4\times 10^4B_c^e`$ (curve II) and $`B_m=1.5\times 10^5B_c^e`$ (curve III). For $`B_m=4\times 10^4B_c^e`$, we note that the curve becomes slightly stiffer with the onset of $`K^{}`$ condensation. This stiffening may be attributed to the large enhancement in electron and muon fraction in the field. However, this effect is reduced in the high density regime where electron and muon fraction become small. As the field is further increased to $`B_m=1.5\times 10^5B_c^e`$, not only electrons and muons are strongly Landau quantized, but also protons are populated in the zeroth Landau level. It was shown  that Landau quantization of charged particles was responsible for the softening in the equation of state. On the other hand, the effects of baryon magnetic moments for $`B_m=1.5\times 10^5B_c^e`$ overwhelm the effects of Landau quantization. Consequently, the curve corresponding to $`B_m=1.5\times 10^5B_c^e`$ stiffens further. It is found here that the effects of magnetic moments are important for $`B_m>10^5B_c^e`$. Besides the effects of Landau quantization and magnetic moments, the contribution of electromagnetic field to the matter energy density and pressure is to be taken into account. The magnetic energy density and pressure, $`\epsilon _f=P_f=B_m^2/(8\pi )=4.814\times 10^8(B_m/B_c^e)^2MeVfm^3`$, become significant in the core of the star for $`B_m10^5B_c^e`$.

In this calculation, we have considered interior magnetic field $`>5\times 10^{18}`$G. However, it was found in a recent calculation  that the maximum value of the magnetic field within a star may not exceed $`3\times 10^{18}`$G for a particular choice of a constant current function but independent of an EoS. In this case, the ratio of the maximum field to the average field is not large because of small spatial gradient. The authors  argued that the value of maximum field at any point may well exceed the average value as mentioned above for a different field geometry. In that event the effects of strong magnetic field $`>5\times 10^{18}`$G on the threshold of antikaon condensation, particle composition and EoS might be important.

To summarise, in this paper, we have focused on the formation of the antikaon condensation in dense nuclear matter in the presence of magnetic fields. We have considered the interaction of magnetic moments of baryons with the field and the magnetic energy density and pressure in this work. In the presence of strong magnetic fields $`>5\times 10^{18}`$G, we find a considerable change in the phase spaces of charged particles. The threshold density of $`K^{}`$ condensation is delayed to higher density in the presence of such a strong field and the EoS becomes stiffer. For $`B_m>10^{18}`$G, the effects of magnetic moments are important and it adds to further stiffening of the equation of state. Also, the electromagnetic field contribution to the energy density and pressure becomes important in the core for $`B_m>10^{18}`$G. The stiffening of the EoS in the presence of magnetic fields might have significant impact on the gross properties of neutron stars such as the mass-radius relationship, cooling etc. It is worth mentioning here that (anti)kaons do not interact with magnetic fields in the same way as fermions do because their spin angular momentum is zero.

In this calculation, we do not include the role of hyperons, pion condensation and nucleon-nucleon correlation on the antikaon condensation. Negatively charged hyperons, in particular $`\mathrm{\Sigma }^{}`$ hyperon, could delay the onset of $`K^{}`$ condensation . However, it was estimated that $`\mathrm{\Sigma }^{}`$-nucleon interaction is highly repulsive in normal nuclear matter . Recently, it has been also shown that threshold densities of most hyperons including $`\mathrm{\Sigma }^{}`$ are substantially increased in strong magnetic field $`B_m>5\times 10^{18}`$G both due to Landau quantisation and magnetic moment interactions . In this situation, $`\mathrm{\Sigma }^{}`$ hyperons might have no impact on $`K^{}`$ condensation. Pion condensation could occur in neutron stars because of the attractive $`p`$-wave pion-nucleon interaction . The condensation of $`\pi ^{}`$ may modify the electron chemical potential which, in turn, would delay $`K^{}`$ condensation. In this paper, we have employed the RMF model which does not include nucleon-nucleon correlations. It was shown in non relativistic models  that nucleon-nucleon correlations shifted the threshold density of $`K^{}`$ condensation to higher density. We believe that the qualitative features of strong magnetic fields presented here would survive even in other models which include hyperons, pion condensation and nucleon-nucleon correlations. It would be interesting to look into the neutrino emissivity from an antikaon condensed matter and the structure of compact stars having antikaon condensate in the presence of a strong magnetic field.

Fig.1 : The particle abundances are plotted with normalised baryon density for $`B_m=0`$ and $`B_m=1.5\times 10^5B_c^e`$. Solid lines indicate particle abundances for field free case whereas dashed lines denote those with the magnetic field. The critical electron field ($`B_c^e`$) is $`4.414\times 10^{13}`$G.

Fig.2 : The matter pressure ($`P`$) is shown as a function of matter energy density ($`\epsilon `$) for different values of $`B_m`$. The field free case is shown by curve I (solid line) and curve II (dash-dotted line) and curve III (dashed line) represent calculations for $`B_m=4\times 10^4B_c^e`$ and $`B_m=1.5\times 10^5B_c^e`$, respectively. The critical electron field ($`B_c^e`$) is $`4.414\times 10^{13}`$G.


text:
# References

Comment on “Confinement of Slave Particles in U(1) Gauge Theories of Strongly Interacting Electrons”

Masaki Oshikawa

Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551 JAPAN

In a recent Letter Nayak1 ; Nayak2 , Nayak argued that the deconfinement can never happen in the U(1) gauge theory approach, because the “holon” charge $`q_b`$ and “spinon” charge $`q_f`$ can be assigned arbitrarily provided $`q_bq_f=e`$ ($`e`$ is the electron charge). This simple but important question seems never answered appropriately IM-comment ; IMO . In this Comment, I shall examine the issue more carefully.

Besides the dynamical gauge field $`a_\mu `$, I introduce (smooth) external static gauge fields $`A_\mu ^f`$ and $`A_\mu ^b`$ which couple respectively to the spinon and holon fields. To obtain the low-energy effective action, high-energy parts of the dynamical fields are integrated out; their low-energy parts are kept fixed and are indistinguishable from the external fields. As a consequence, under $`A^f`$ and $`A^b`$, the effective action must be written in terms of $`\stackrel{~}{A}_\mu ^\alpha A_\mu ^\alpha +a_\mu `$. Here I assume that the kinetic term of the gauge field is generated in the low energy effective action, as it is argued in the U(1) gauge theory approach. The low-energy effective Lagrangian density is thus written as

$``$ $`=`$ $`_f[\overline{f}_\sigma ,f_\sigma ,\stackrel{~}{A}_\mu ^f]+_b[\overline{b},b,\stackrel{~}{A}_\mu ^b]+{\displaystyle \frac{\lambda _f}{4}}\stackrel{~}{F}_{\mu \nu }^f\stackrel{~}{F}_{\mu \nu }^f`$ (1)
$`+{\displaystyle \frac{\lambda _m}{2}}\stackrel{~}{F}_{\mu \nu }^f\stackrel{~}{F}_{\mu \nu }^b+{\displaystyle \frac{\lambda _b}{4}}\stackrel{~}{F}_{\mu \nu }^b\stackrel{~}{F}_{\mu \nu }^ba_\mu J_\mu ^0,`$
where $`J_\mu ^0`$ represents the constant density of one particle per site. Here $`\stackrel{~}{F}_{\mu \nu }^\alpha =_\mu \stackrel{~}{A}_\nu ^\alpha _\nu \stackrel{~}{A}_\mu ^\alpha `$ ($`\alpha =f,b`$) and $`\lambda _{f,m,b}`$ are coupling constants. In the limit of zero external fields, we recover the usual form with the gauge field coupling constant $`g^2=\lambda _f+2\lambda _m+\lambda _b`$.

In the low-energy effective theory, one may consider the currents $`J^{f,b}`$ defined by the functional derivative of the action by the external fields $`A^{f,b}`$. The equation of motion of the dynamical gauge field $`a_\mu `$ leads to the “confinement constraint” $`J_\mu ^f+J_\mu ^b=J_\mu ^0`$. However, these currents actually includes a contribution from the gauge field: $`J_\mu ^f=j_\mu ^f+\lambda _f_\nu \stackrel{~}{F}_{\mu \nu }^f+\lambda _m_\nu \stackrel{~}{F}_{\mu \nu }^b`$, where $`j_\mu ^f=_f/A_\mu ^f`$ is the spinon current is in a standard definition. The current $`j^b`$ is similarly defined. The currents $`j^\alpha `$ do not obey the confinement constraint.

To discuss the charge of the particles, I set $`A_\mu ^f=q_fA_\mu ,A_\mu ^b=q_bA_\mu `$, where $`A_\mu `$ is the physical electromagnetic vector potential which is regarded as an external field in this Comment. Starting from the tentative assignment $`q_f=0`$ and $`q_b=e`$, the redefinition of the gauge field as $`a_\mu a_\mu +ceA_\mu `$ with an arbitrary parameter $`c`$ induces the change in the charges Nayak1 ; Nayak2  $`q_f=ce`$ and $`q_b=(c+1)e`$. The physical current reads, after the redefinition, $`J_\mu ^{em}=ceJ_\mu ^f+(1+c)eJ_\mu ^bceJ_\mu ^0`$. This apparently depends on the arbitrary parameter $`c`$. However, the dependence on $`c`$ turns out to be proportional to $`J_\mu ^f+J_\mu ^bJ_\mu ^0`$, which vanishes thanks to the equation of motion. Thus the physical current is indeed independent of the charge assignment, as it should be.

What is the charge of a slave particle, if it is deconfined? For simplicity, below I take the limit of zero external field. The total physical current is given by $`J_\mu ^{em}=eJ_\mu ^b=ej_\mu ^b+e(\lambda _m+\lambda _b)_\nu f_{\mu \nu },`$ independent of $`c`$. Let us suppose that the spinon current $`j_\mu ^f`$ is changed by $`\delta j_\mu ^f`$ while $`j_\mu ^b`$ is kept fixed. The change $`\delta j_\mu ^f`$ affects the gauge field through the equation of motion, and the total change induced in the physical current reads $`\delta J_\mu ^{em}=e\frac{\lambda _m+\lambda _b}{\lambda _f+2\lambda _m+\lambda _b}\delta j_\mu ^f`$. This means that, the effective charge of a deconfined spinon, including the contributions from the gauge field, is given by $`Q_f=e(\lambda _m+\lambda _b)/(\lambda _f+2\lambda _m+\lambda _b)`$ which is independent of the arbitrary parameter $`c`$ of charge assignment. A similar analysis gives the effective charge of a deconfined holon $`Q_b`$, which satisfies $`Q_bQ_f=e`$.

To conclude, the arbitrariness in the charge assignment observed by Nayak does not contradict with the possibility of the deconfinement. The effective charge carried by a deconfined slave particle appears to be fractional, which is independent of the arbitrary charge assignment but is rather determined dynamically. This fractional charge is apparently not quantized, unlike in the fractional quantum Hall effect. An estimate based on the one-loop calculation (see e.g. NL ) shows PAL  that $`Q_b`$ and $`Q_f`$ are proportional to $`(1x)`$ and $`x`$ respectively, where $`x`$ is the doping concentration. This implies that the “holon” indeed carries most (but not all!) of the charge near half filling ($`x1`$). More reliable non-perturbative calculations of the effective charges $`Q_\alpha `$, along with the examinations on whether the deconfinement really takes the place, would be desired.

I thank Kazusumi Ino, Patrick A. Lee and Chetan Nayak for useful discussions. This work is supported in part by Grant-in-Aid from MEXT of Japan.