text:
# Minimizing the Stabbing Number of Matchings, Trees, and TriangulationsAn extended abstract appeared in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms [11].

## 1 Introduction

#### Objective Functions.

Many problems in combinatorial optimization, algorithmic graph theory, or computational geometry deal with minimizing the length of a desired structure: given a set of vertices, find a set of line segments of small total length, such that a certain structural condition is maintained. Among the most popular structures are spanning trees, perfect matchings, or (in a planar geometric setting) triangulations of minimum total length. Other geometric problems give rise to other objective functions: for example, one can ask for the total turn cost between adjacent line segments; e.g., see .

When dealing with structural or algorithmic properties, another possible objective function is the stabbing number: for a given set of line segments, this is the maximum number of segments that are encountered (in their interior or at an endpoint) by any line. If we consider only axis-parallel lines, we get the axis-parallel stabbing number. A closely related measure defined by Matoušek  is the crossing number, which is the number of connected components of the intersection of a line with the union of line segments111This should not be confused with the crossing number in graph drawing, which is the total number of crossing line segments.. If there are no connected components of collinear segments (which is the case for matchings), the crossing number coincides with the stabbing number. When considering structures like triangulations, the crossing number is precisely one more than the maximum number of triangles intersected by any one line.

Stabbing problems have been considered for several years. The complexity of many algorithms in computational geometry is directly dependent on the complexity of ray shooting; as described by Agarwal , the latter can be improved by making use of spanning trees of low stabbing number. We will sketch some related results further down. Most previous work on stabbing and crossing problems has focused on extremal properties, and little has been known about the computational complexity of actually finding structures of low stabbing number, or possible approximation algorithms. In fact, settling the complexity of Minimum Stabbing Number for spanning trees has been one of the original 30 outstanding open problems of computational geometry on the list by Mitchell and O’Rourke . (An up-to-date list is maintained online by Demaine, Mitchell, and O’Rourke .)

#### Our Contributions.

We describe a general proof technique that shows $`𝒩𝒫`$-hardness of minimizing the stabbing number of perfect matchings, triangulations, and spanning trees. For the case of matchings we show that it is also hard to approximate the minimum stabbing number within a factor below 6/5.

On the other hand, we present a mathematical programming framework for actually finding structures with small stabbing number. Our approach characterizes solutions to stabbing problems as integer programs (IPs) with an exponential number of cut constraints. We describe how the corresponding linear programming (LP) relaxations can be solved in polynomial time, providing empirically excellent lower bounds. Furthermore, we show that there always is an optimal fractional matching (or spanning tree) that contains an edge of weight above a lower bound of 1/3 (or 1/5 for spanning trees), allowing an iterated rounding scheme similar to the one developed by Jain for the generalized Steiner network problem : compute a heuristic solution by solving a polynomial number of LPs. We conjecture that the objective function value of this heuristic solution is within a constant factor of the optimum. Our mathematical programming approach is also practically useful: as described in detail in our experimental study , we can optimally solve stabbing problems for instances (taken from well-known benchmark sets of other geometric optimization problems) of vertex sets up to several hundred vertices.

Our results in detail:

* We prove that deciding whether a vertex set has a perfect matching of axis-parallel stabbing number 5 is an $`𝒩𝒫`$-complete problem; we also extend this result to general stabbing number.
* We prove that finding a triangulation of minimum axis-parallel stabbing number is an $`𝒩𝒫`$-hard problem; we also extend this result to general stabbing number.
* We prove that finding a spanning tree of minimum axis-parallel stabbing number is an $`𝒩𝒫`$-hard problem; we extend this result to general stabbing number, and sketch $`𝒩𝒫`$-hardness proofs for minimum axis-parallel or general crossing number.
* We give an IP-based formulation for stabbing problems; the corresponding fractional LP solutions can be computed in polynomial time, providing a family of lower bounds.
* We give results on the structure of fractional vertices of the resulting LP relaxation: for matching, we show that there always is an edge with weight at least $`1/5`$, while for spanning trees, there always is an edge with weight greater than $`1/3`$. This gives way to a heuristic algorithm based on iterated rounding; we conjecture that the resulting solution values are within a constant factor of the optimum.

The vertex sets constructed in our hardness proofs make critical use of the collinearity of vertices. On the other hand, our positive (LP-based) results do not make any assumptions on the structure of the vertex set: they can be used for vertex sets in degenerate as well as in general position, and can be applied to any family of stabbing lines that can be evaluated by considering a subset of polynomially many representatives.

We have also performed a computational study on a diverse set of instances; the results show that our LP-based approach is good not only in theory (where we get a polynomial running time based on the ellipsoid method), but also for actually solving instances in practice (where we use the simplex method). Details are omitted from this theoretical paper; a report on the practical results can be found in .

#### Related Work.

Existing work dealing with structures of low stabbing number can be divided into algorithmic applications and implications on one hand, and extremal properties on the other hand.

Agarwal  describes improved algorithmic solutions for problems such as ray shooting and implicit point locations queries (which by themselves have applications in polygon containment, implicit hidden surface removal, polygon placement, etc.); his main tool are spanning trees with low stabbing number. One of the theoretically best performing data structures for ray tracing in two dimensions is based on a triangulation of the polygonal scene; see Hershberger and Suri : in their “pedestrian” approach to ray shooting, the complexity of a query is simply the number of triangles visited, i.e., corresponds precisely to the stabbing number. Held, Klosowski, and Mitchell  investigate collision detection in a virtual reality environment, again, based on “pedestrian” ray shooting. More recently, Aronov et al.  have performed an experimental study of the complexity of ray tracing algorithms and run-time predictors, which include average number of intersection points for a transversal line, and depth complexity.

Extremal properties of crossing numbers were considered by Welzl  and by Matoušek , who showed that any planar set of $`n`$ vertices has a spanning tree with a crossing number of $`O(\sqrt{n})`$, and provided examples requiring a crossing number of $`\mathrm{\Omega }(\sqrt{n})`$. Another variant is studied by de Berg and van Kreveld : the stabbing number of a decomposition of a rectilinear polygon $`P`$ into rectangles is the maximum number of rectangles intersected by any axis-parallel segment that lies completely inside of $`P`$; they prove that any simple rectilinear polygon with $`n`$ vertices admits a decomposition with stabbing number $`O(\mathrm{log}n)`$, and they give an example of a simple rectilinear polygon for which any decomposition has stabbing number $`\mathrm{\Omega }(\mathrm{log}n)`$. They generalize their results to rectilinear polygons with rectilinear holes. Agarwal, Aronov, and Suri  investigate extremal properties of the stabbing number of triangulations in three dimensions, where the stabbed objects are simplices; see also Aronov and Fortune  for this problem. Shewchuk  shows that in $`d`$ dimensions, a line can stab the interiors of $`\mathrm{\Theta }(n^{d/2})`$ Delaunay $`d`$-simplices. This implies, in particular, that a Delaunay triangulation in the plane may have linear stabbing number. More recently, Tóth  showed that for any subdivision of $`d`$-dimensional Euclidean space, $`d2`$, by $`n`$ axis-aligned boxes, there is an axis-parallel line that stabs at least $`\mathrm{\Omega }(\mathrm{log}^{1/(d1)}n)`$ boxes, which is the best possible lower bound. Generalizations of the stabbing objects have also been considered: most notably, Chazelle and Welzl  describe extremal properties of stabbing spanning trees in $`d`$-dimensional space by hyperplanes; the analogous problem and a corresponding result for matchings is also discussed in .

#### This Paper.

The rest of this paper is organized as follows. After some basic definitions and notation in Section 2, we give details of our various hardness proofs in Section 3. In Section 4, we describe our LP-based approach for constructing bounds. Section 5 presents an iterated rounding technique for matching and spanning tree problems; we believe that the resulting algorithms yield constant-factor approximations. Final concluding thoughts and miscellaneous results and problems are presented in Section 6.

## 2 Preliminaries

Given a set $`L`$ of line segments in the plane, the *stabbing number* of a line $`\mathrm{}`$ is the number of segments of $`L`$ that are intersected by $`\mathrm{}`$. The *stabbing number of* $`L`$ is the maximum stabbing number over all lines $`\mathrm{}`$; the *axis-parallel stabbing number of* $`L`$ is the maximum stabbing number over all axis-parallel lines $`\mathrm{}`$. In this paper, the set $`L`$ will arise as the edges of a perfect matching, spanning tree, or triangulation of a given set $`P`$ of $`n`$ vertices in the plane, and our objective is to find such a structure of minimum stabbing number. Any reference to matching always means perfect matching. Therefore, when dealing with matchings, we assume that $`n`$ be even, if necessary by omitting one of the vertices.

We denote by $`\text{St-Mat}(P)`$ the minimum stabbing number among all matchings of $`P`$, by $`\text{St-Tre}(P)`$ the minimum stabbing number of all spanning trees of $`P`$, and by $`\text{St-}\mathrm{\Delta }(P)`$ the minimum stabbing number of all triangulations of $`P`$. We use $`\text{St-Mat}_2(P)`$, $`\text{St-Tre}_2(P)`$, and $`\text{St-}\mathrm{\Delta }_2(P)`$ for the minimum axis-parallel stabbing numbers.

For a set $`L=\{l_1,\mathrm{},l_n\}`$ of line segments in the plane, the crossing number of a line $`\mathrm{}`$ is the number of connected components of $`_{i=1}^nl_i\mathrm{}`$. The crossing number of $`L`$ is the maximum crossing number over all lines $`\mathrm{}`$; just like for the stabbing number, the axis-parallel crossing number is defined for axis-parallel lines. For matchings, trees, and triangulations, we use the analogous abbreviations $`\text{Cr-Mat}(P)`$, $`\text{Cr-Tre}(P)`$, and $`\text{Cr-}\mathrm{\Delta }(P)`$, and their subscripted counterparts $`\text{Cr-Mat}_2(P)`$, $`\text{Cr-Tre}_2(P)`$, and $`\text{Cr-}\mathrm{\Delta }_2(P)`$ for the axis-parallel crossing numbers. Note that stabbing and crossing number coincide for planar matchings.

## 3 Complexity

In this section we prove $`𝒩𝒫`$-hardness of computing the minimum stabbing number of matchings and computing the minimum crossing number of triangulations; for spanning trees the proofs are analogous, and we only give a sketch of the proof. Our technique is rather general and should be applicable to other structures and variants as well.

### 3.1 Perfect Matchings

###### Theorem 1

Deciding whether $`\text{St-Mat}_2(P)5`$ is strongly $`𝒩𝒫`$-complete.

Proof. Clearly, the problem is in $`𝒩𝒫`$. We show completeness using a reduction from 3SAT . Assume we have a Boolean expression denoted by $`B(x_0,x_1,\mathrm{},x_{n1})`$ with $`n`$ variables and $`k`$ clauses of three literals each. We construct a set of vertices $`P`$ that has a perfect matching $`M`$ of stabbing number 5 if and only if the Boolean expression can be satisfied; in case of an unsatisfiable expression, a stabbing number of at least 6 cannot be avoided.

Consider the overall layout of $`P`$ as shown in Figure 1. We make critical use of the collinearity of vertices, using up all of the available stabbing number of 5 in a particular direction. Thus we are able to construct “barriers” which avoid any interference between the different gadgets.

At the top of the layout are two groups of 10 vertices. The vertices in a group of 10 have the same $`y`$-coordinate. We call these two groups the *top rows*. The $`i`$-th vertex in the first top row has the same $`x`$-coordinate as the $`i`$-th vertex in the second top row. Below the top rows are $`n`$ groups of 6 vertices. All vertices in a group of 6 have the same $`x`$-coordinate, as shown in the figure. The vertical lines through these groups of 6 vertices separate the variables from each other and from other vertices left of the variables. We call each such group a *vertical barrier* gadget. The vertices in barrier $`i`$ are sufficiently far below the vertices in barrier $`i+5`$ to ensure that horizontal lines through the vertical barriers have stabbing number at most 5. The barriers lie between vertical lines through the last and second last vertices of the top rows. To the left of the top rows and below the vertical barriers are $`k+1`$ groups of 10 vertices. Each vertex in a group of 10 has the same $`y`$-coordinate. We call each such group a *horizontal barrier* gadget. The vertices in barrier $`i`$ are sufficiently far to the right of the vertices in barrier $`i+5`$ to ensure that vertical lines through the horizontal barriers have stabbing number at most 5. The horizontal barriers are used to separate clauses from each other, to separate the clauses from the variables, and to separate variables from other vertices above the variables. Between and to the right of the top two horizontal barriers are groups of 8 vertices. Each vertex in a group of 8 has the same $`y`$-coordinate. We call each such group a *reducer* gadget of a variable. The vertices in reducer $`i`$ are far enough to the right of the vertices in reducer $`i+1`$ to ensure that vertical lines through the reducers have stabbing number at most 5.

Figure 2 shows a set of 6 vertices, numbered $`i_0`$ to $`i_5`$ in clockwise order, that represents a variable. These variable gadgets are separated by vertical barriers, and are placed below the vertical barriers, between the top two horizontal barriers and to the right of the reducers. Variables are placed such that the $`y`$-coordinate of the horizontal line through the reducer of a variable is in between the $`y`$-coordinate of vertices $`i_0`$ and $`i_5`$ of that variable. The strip formed by vertical lines between vertices $`i_0`$ and $`i_1`$ of variable $`x_i`$ is called the *$`x_i`$-column* of the variable. The strip formed by vertical lines between vertices $`i_1`$ and $`i_2`$ of variable $`x_i`$ is called the *$`\overline{x}_i`$-column* of the variable.

The horizontal and vertical barriers create $`kn`$ locations for literal gadgets. These are groups of 4 vertices representing the occurrence of a variable in a clause. Each group of 4 vertices forms an axis-parallel square. If a literal $`x_i`$ appears in the clause $`c_j`$, we place a literal gadget in the $`x_i`$ column of clause $`c_j`$. If a literal $`\overline{x}_i`$ appears in the clause $`c_j`$, we place a literal gadget in the $`\overline{x}_i`$ column of clause $`c_j`$. The three literal gadgets for a clause are put on the same horizontal lines. The literal in column $`x_i`$ of clause $`c_j`$ is to the left of the literal in column $`x_i`$ of clause $`c_h`$ for $`j<h`$. Similarly, the literal in column $`\overline{x}_i`$ of clause $`c_j`$ is to the left of the literal in column $`\overline{x}_i`$ of clause $`c_h`$ for $`j<h`$. Figure 3 shows the literals of two clauses.

We first assume that $`B(x_0,x_1,\mathrm{},x_{n1})`$ is satisfiable, and show that $`P`$ has a matching $`M`$ of stabbing number 5. We connect vertex $`i`$ to vertex $`i+1`$ in each of the two top rows for $`i=0,2,4,6,8`$. We connect vertex $`i`$ to vertex $`i+1`$ in each vertical barrier for $`i=0,2,4`$. We connect vertex $`i`$ to vertex $`i+1`$ in each horizontal barrier for $`i=0,2,4,6,8`$. We connect vertex $`i`$ to vertex $`i+1`$ in each reducer for $`i=0,2,4,6`$.

If the variable $`x_i`$ has the value *true*, we connect the pairs $`(i_0,i_5)`$, $`(i_1,i_2)`$, and $`(i_3,i_4)`$ of the variable. If the variable $`x_i`$ has the value *false*, we connect the pairs $`(i_0,i_1)`$, $`(i_2,i_3)`$, and $`(i_4,i_5)`$. Notice that if $`x_i`$ is *true*, then any vertical line in the $`x_i`$-column stabs 2 edges in the top rows of $`M`$, and a vertical line in the $`\overline{x}_i`$-column stabs 2 edges in the top row and 2 edges in the rectangle of the variable. If $`x_i`$ is *false*, this situation is reversed. The column with vertical stabbing number 2 is called the *true*-column of the variable, the column with vertical stabbing number 4 is called the *false*-column. In each literal gadget representing the value *true* we connect the four vertices with two horizontal edges. In each literal gadget representing the value *false* we connect the four vertices with two vertical edges.

We can now verify that $`M`$ has stabbing number 5. Any vertical line in the *true*-column of variable $`x_i`$ stabs two edges in the top rows and at most two edges in a literal. Any vertical line in the *false* column stabs two edges in the top rows, two edges of the variable and at most one in a literal. Any horizontal line in a clause stabs at most three literal gadgets, one of which is set to *true*. So these lines stab at most 5 edges of $`M`$. It can easily be verified that all other horizontal and vertical lines stab at most 5 edges from $`M`$.

Conversely, we assume that $`P`$ has a matching of stabbing number 5. We show that $`B`$ is satisfiable. The matching used in this proof is illustrated in Figures 1, 2 and 3. Because the top rows contain 10 vertices, these vertices have to be connected to each other, otherwise the stabbing number of $`P`$ exceeds $`5`$. There are several ways to connect the sets of 10 vertices. If we connect vertex $`i`$ to vertex $`i+1`$ for $`i=0,2,4,6,8`$ in each row, the number of edges stabbed by any horizontal or vertical line is minimized. Therefore we may assume without loss of generality that these edges are in the matching $`M`$. Collinear vertices are dealt with in a similar manner: If there are several ways to connect a set of collinear vertices, we will prefer connections that have minimal stabbing number for all stabbing lines.

Thus, we can connect vertex $`i`$ to vertex $`i+1`$ for $`i=0,2,4,6,8`$ in each horizontal barrier gadget. For the same reason, we can connect vertex $`i`$ to vertex $`i+1`$ for $`i=0,2,4,6`$ in each reducer gadget. Because vertical lines through the vertical barrier gadgets stab two edges in the top rows, we can connect vertex $`i`$ to vertex $`i+1`$ for $`i=0,2,4`$ in each vertical barrier gadget.

Now it is easy to see that no vertex in a variable or literal gadget for some variable $`x_i`$ can be matched with any vertex not involved with representing the same variable $`x_i`$: otherwise, the edge would cross a line through a vertical barrier, which already crosses another five edges. Furthermore, such a vertex must be matched with vertices from the same gadget (either the same variable gadget or the same literal gadget): otherwise, we get a violation at a line through a horizontal barrier gadget.

Now each reducer gadget contributes four to a horizontal stabbing number. Thus, we cannot connect the six vertices of a variable $`x_i`$ by three vertical edges. Figure 2 shows the two remaining, essentially distinct matchings.

Of the three literals in each clause, one has to be set to true, otherwise there will be a horizontal stabber intersecting six edges. The true literal, say, $`x`$, must lie in a *true*-column of a variable, because vertical lines in this column have stabbing number two. Any other literal in this column can also be set to *true*. The literals $`\overline{x}`$ lie in the *false*-column of the same variable, and have to be set to false. So if a matching of stabbing number five exists, there is a truth assignment of the Boolean expression. $`\mathrm{}`$

###### Corollary 2

There is no $`\alpha `$-approximation algorithm for $`\text{St-Mat}_2(P)`$ with $`\alpha <6/5`$; in particular there is no polynomial time approximation scheme (PTAS), unless $`𝒫=𝒩𝒫`$.

###### Corollary 3

Computing $`\text{St-Mat}(P)`$ is a weakly $`𝒩𝒫`$-hard problem.

Proof. We apply a perturbation technique, similar to the one in . We start with the same basic construction as for the hardness proof for the axis-parallel case, and consider the grid formed by the coordinates of the resulting vertex set. This grid is modified such that the interpoint distances between the vertices of the same gadget are $`\mathrm{\Theta }(\epsilon ^{n^2+2})`$ for the literal gadgets and $`\mathrm{\Theta }(\epsilon ^{n^2})`$ for all other gadgets. Furthermore, the rest of the grid is perturbed by powers of $`\epsilon `$, such that only axis-parallel lines can stab more than two gadgets; in particular, we increase the vertical distance between variable gadgets and the (narrower) literal gadgets by a sufficient amount, in order to make sure that no line through two literal gadgets for the same variable can intersect the corresponding variable gadget. Now it is easy to see that lines that are not axis-parallel can stab at most four line segments, leaving only axis-parallel lines as critical. $`\mathrm{}`$

### 3.2 Triangulations

Our basic proof technique is the same as for matchings. We first describe the construction of barrier gadgets, using the following terminology. A *horizontal line* is given by a set of vertices that are horizontally collinear. A *vertical line* is given by a set of vertically collinear vertices. A *row* consists of two horizontal lines, and the (empty) space between them. A *column* consists of two vertical lines, and the (empty) space between them.

###### Lemma 4

Consider a row consisting of two horizontal lines $`l_a`$ and $`l_b`$ in $`P`$, having $`a`$ and $`b`$ vertices, respectively. If the combined number of edges on $`l_a`$ and $`l_b`$ is $`a+bi2`$, then a horizontal stabber between $`l_a`$ and $`l_b`$ encounters at least $`a+b+i2`$ triangles in any triangulation of $`P`$ and its crossing number is at least $`a+b+i1`$.

Proof. Assume without loss of generality that $`l_a`$ lies above $`l_b`$. Suppose there are $`ai_a1`$ edges on the line $`l_a`$ and $`bi_b1`$ edges on the line $`l_b`$ with $`i_a+i_b=i`$. For each edge $`(u,v)`$ on $`l_a`$ there is a triangle $`(u,v,w)`$ where $`w`$ lies either on or below $`l_b`$. Let $`A`$ denote this set of triangles. Similarly, for each edge $`(u,v)`$ on $`l_b`$ there is a triangle $`(u,v,w)`$ where $`w`$ lies either on or above $`l_a`$. Let $`B`$ denote this set of triangles. For each two neighboring vertices $`u`$ and $`v`$ on $`l_a`$ for which there is no edge $`(u,v)`$ there are triangles $`(u,u_0,u_1)`$ and $`(v,v_0,v_1)`$ such that $`u_0`$ and $`v_0`$ lie on or below $`l_b`$ and $`u_1`$ and $`v_1`$ lie above $`l_a`$. Let $`I_a`$ denote this set of triangles. Also for each two neighboring vertices $`u`$ and $`v`$ on $`l_b`$ for which there is no edge $`(u,v)`$ there are triangles $`(u,u_0,u_1)`$ and $`(v,v_0,v_1)`$ such that $`u_0`$ and $`v_0`$ lie on or above $`l_a`$ and $`u_1`$ and $`v_1`$ lie below $`l_b`$. Let $`I_b`$ denote this set of triangles. It is not hard to verify that any two of the the four sets of triangles $`A`$, $`B`$, $`I_a`$ and $`I_b`$ have an empty intersection. A horizontal line $`l`$ between $`l_a`$ and $`l_b`$ stabs every triangle in $`A`$, $`B`$, $`I_a`$ and $`I_b`$. So $`l`$ stabs at least $`|A|+|B|+|I_a|+|I_b|`$ $`=(ai_a1)+(bi_b1)+2i_a+2i_b`$ $`=a+b+i2`$ triangles and $`a+b+i1`$ edges. $`\mathrm{}`$

The lemma holds analogously for two vertical lines that form a column. When a row consists of two horizontal lines that have $`\text{Cr-}\mathrm{\Delta }_2(P)+1`$ vertices altogether, we call it *full* or fully triangulated. It follows from the lemma that all $`\text{Cr-}\mathrm{\Delta }_2(P)1`$ edges on the lines $`l_a`$ and $`l_b`$ have to be present.

###### Theorem 5

Finding $`\text{Cr-}\mathrm{\Delta }_2(P)`$ is $`𝒩𝒫`$-hard.

Proof. Again we use a reduction from 3SAT, and the proof proceeds along the lines of the proof of Theorem 1. See Figure 4 for a schematic layout of a representing vertex set $`P`$ for the 3SAT instance $`B(x_0,x_1,x_2)=(x_0x_1\overline{x}_2)(x_0\overline{x}_1x_2)(\overline{x}_0\overline{x}_1\overline{x}_2)`$. Figure 5 shows the structure of variable gadgets.

For a given Boolean expression $`B(x_0,x_1,\mathrm{},x_{n1})`$ with $`n`$ variables and $`k`$ clauses of three literals each we construct a set $`P`$ of vertices. We show that there is a value $`K`$ such that $`B`$ is satisfiable only if $`\text{Cr-}\mathrm{\Delta }_2(P)=2K1`$; if $`B`$ cannot be satisfied, $`\text{Cr-}\mathrm{\Delta }_2(P)`$ is at least $`2K`$.

In Figure 4 we have $`K=39`$ and a grid of vertices with some well-defined holes. The maximum number of vertices in a horizontal or vertical line is $`K`$, and many lines have exactly $`K`$ vertices. By Lemma 4 a full row or column in this setting has exactly $`2K2`$ triangles. Gadgets are separated by full rows and columns.

Figure 5 shows two horizontally aligned rectangles of eight vertices each that together represent a variable $`x_i`$. We call the strip formed by vertical lines that stab the left rectangle the $`x_i`$-column, and the strip formed by vertical lines that stab the right rectangle the $`\overline{x}_i`$-column of the variable. The gadget works essentially the same way as that in Figure 2. Each rectangle has full rows and columns as neighbors. We indicate how this can be achieved in horizontal direction in Figure 5. By Lemma 4 we conclude that all edges on the boundary of the convex hull of each rectangle are present in any triangulation of minimal crossing number. The horizontal lines that contain the top and bottom lines of the two rectangles, respectively, contain $`K`$ vertices each; the horizontal line that passes through the middle of the rectangles contains $`K1`$ vertices. Therefore Lemma 4 shows that exactly one edge along this horizontal line in the middle of the rectangle may be missing. We call the strip that is spanned by all vertical lines that stab the rectangle with the missing horizontal edge the *true*-column of the variable $`x_i`$. The strip that is spanned by all vertical lines that stab the rectangle for which the middle horizontal edge is present is the *false*-column of the variable $`x_i`$. As shown in Figure 4, any satisfying literal adds exactly one less to the vertical crossing number than an unsatisfied one. In the overall layout, variable $`x_i`$ is placed below and to the left of variable $`x_j`$ for $`i<j`$ in such a way that variables are vertically separated from one another by a full row, and horizontally separated from one another by a full column.

Each literal is represented by a square with eight vertices on its boundary. We make the width of rectangles of the variables equal to a power of two, and wide enough to accommodate the necessary number of literals. That is, each rectangle of a variable is of a width at most four times the number of occurrences of the most frequent literal in $`B`$. Figure 5 gives a hint at how this widening of a rectangle is done. Notice that if the most frequent literal in $`B`$ occurs $`t`$ times, there are $`\mathrm{\Theta }(\mathrm{log}t)`$ rows above and below the variable so that in the top and bottom lines of these groups of rows the vertices above and below the variables are a distance of one apart. The three literals of a clause $`c_j`$ are horizontally aligned, and the two rows that are spanned by them are called the clause $`c_j`$. Clauses are separated from each other by full rows. If a literal $`x_i`$ appears in the clause $`c_j`$, we place a literal gadget in the $`x_i`$-column of the clause gadget $`c_j`$. If a literal $`\overline{x}_i`$ appears in the clause $`c_j`$, we place a literal gadget in the $`\overline{x}_i`$-column of the clause gadget $`c_j`$. The literal in column $`x_i`$ of clause $`c_j`$ is to the left of the literal in column $`x_i`$ of clause $`c_h`$ for $`j<h`$. Similarly, the literal in column $`\overline{x}_i`$ of clause $`c_j`$ is to the left of the literal in column $`\overline{x}_i`$ of clause $`c_h`$ for $`j<h`$. So no vertical line stabs the interior of more than one literal.

By adding vertices to the right of the literals we ensure that a horizontal line through the top or bottom row of the three literals of a clause has exactly $`K`$ vertices, and a horizontal line through the middle horizontal line of the three literals of a clause has exactly $`K2`$ vertices. So two edges along these middle lines may be missing in a triangulation of minimum crossing number, but no more than two. As we will argue later, these edges will be missing in the interior of at most two of the literals. We call the missing of the horizontal middle edge in a literal the *false* setting of the literal, and the presence of this edge within a literal the *true* setting of the literal.

Because the rows above and below a variable are full, we can assume that they are triangulated as shown in Figure 5, because any other triangulation would result in strictly higher vertical crossing numbers. So the *true* column of a variable has a vertical crossing number that is one less than the crossing number of a *false* column. In adding vertices at the bottom of the clauses we ensure the following vertical vertex counts. First of all, the columns neighboring the variables have to be full; in particular, vertical lines that stab the left or the right vertices of a variable rectangle have $`K`$ vertices each. All other vertical lines through a variable should get a number of vertices so that if the corresponding column of the variable is set to *false*, all remaining edges on these vertical lines have to be present. This implies that if the column is set to *true*, we can have one missing edge in the vertical line to the right of the left boundary of the rectangle, and if this edge is missing, there cannot be a missing edge in the next vertical line, one edge missing in the next line, etc.

Let $`B(x_0,x_1,\mathrm{},x_{n1})`$ be satisfiable. We show that $`P`$ has a triangulation of crossing number $`2K1`$ that is minimum by Lemma 4. All full rows and full columns are fully triangulated. If variable $`x_i`$ has the value *true*, we triangulate the interior of the two rectangles of variable $`x_i`$ in such a way that the $`x_i`$-column becomes this variable’s *true*-column, and the $`\overline{x}_i`$-column becomes this variable’s *false*-column. The triangulation of the interior of the rectangles is reversed when variable $`x_i`$ has the value *false*. We set each literal that represents the value *true* to its *true* setting, and set each literal that represents the value *false* to its *false* setting. The triangulation can be completed arbitrarily.

We can now convince ourselves that such a triangulation of $`P`$ indeed attains $`\text{Cr-}\mathrm{\Delta }_2(P)=2K1`$. No fully triangulated row or column has a crossing number larger than $`2K1`$. Because exactly one edge is missing in the horizontal middle line of each variable, Lemma 4 implies that the crossing numbers of the two rows of a variable are both equal to $`(2K1)+11=2K1`$. In each clause there is at least one literal in its *true* setting. Therefore, we can afford two extra triangles caused by the *false* setting of the other two literals in the clause, and no row of a clause intersects more than $`2K2`$ triangles. Finally, we may have one edge missing on the vertical lines passing trough the middle of a literal only in a *true*-column. This condition holds by definition of the setting of the literals according to the truth value of the variables. The “arbitrary completion” of the triangulation only happens in the lower right of the construction. In this corner, vertical and horizontal lines have a low vertex count (except for the boundary), and the allowed crossing number is not exceeded.

For seeing the converse, assume that there is a triangulation of $`P`$ that has crossing number $`2K1`$. We show that $`B`$ is satisfiable. Because a full row or column can be triangulated in such a way that the crossing number of $`2K1`$ is not exceeded, we only have to take care of the rows and columns in which we have a degree of freedom, and where the vertex count is critical by Lemma 4. Because both the top row and the bottom row of a clause have $`2K2`$ vertices, we can afford at most two literals of each clause set to *false*. One literal in each clause has to be set to *true*. The *true* literal has to be in a *true*-column of a variable, for otherwise the vertical crossing number would exceed $`2K1`$. Any other literal in this column can also be set to *true*. The horizontal vertex count of the horizontal lines of the variable forces the second column of this variable to be a *false*-column. In order not to exceed the allowed crossing number in vertical direction, all literals in this column have to be set to *false*. As one easily checks, this yields a consistent setting of the variables, and $`B`$ is satisfiable.

Finally, the size of our construction is indeed polynomial: let $`n`$ and $`c`$ be the number of variables and clauses of $`B(x_0,x_1,\mathrm{},x_{n1})`$. Let $`t`$ be the number of times the most frequent literal in used in $`B`$. A rectangle that represents a variable has width at most $`4t`$ and requires $`\mathrm{\Theta }(\mathrm{log}t)`$ rows. The number of rows used by the clauses is $`\mathrm{\Theta }(c)`$. In order to achieve the correct vertex count in each line we may have to add vertices to the right and below, which requires at most $`\mathrm{\Theta }(t)`$ additional rows and columns. Therefore $`K`$ is polynomial in $`n`$, $`c`$ and $`t`$. $`\mathrm{}`$

### 3.3 Spanning Trees

The basic construction for showing hardness of finding a spanning tree of minimum stabbing number is similar to the one for matchings. As before, we use barriers to restrict possible connections: we make use of the arrangement shown in Figure 6, which works as a barrier gadget because of the following lemma.

###### Lemma 6

Consider three parallel lines, $`\mathrm{}_1`$, $`\mathrm{}_2`$, $`\mathrm{}_3`$, with a set $`S_i`$ of $`k`$ vertices on line $`\mathrm{}_i`$, $`i=1,2,3`$; let $`S=S_1S_2S_3`$. Consider $`PS`$ and a spanning tree $`T`$ of $`P`$ with stabbing number $`k+1`$. Then no edge of $`T`$ crosses the strip spanned by the three lines.

Proof. See Figure 6. Consider a spanning tree $`T`$ of $`P`$, with $`vPS`$ lying outside of the strip. Orient all edges of $`T`$ towards $`v`$. Each vertex in $`S`$ must have outdegree 1, meaning that there are $`k`$ outgoing edges for each of $`S_1`$, $`S_2`$, $`S_3`$, contributing $`k`$ to the stabbing numbers along $`\mathrm{}_1`$, $`\mathrm{}_2`$, $`\mathrm{}_3`$. One of the outgoing edges of $`S_2`$ must intersect $`\mathrm{}_1`$ or $`\mathrm{}_3`$ in order to connect $`S_2`$ to the rest of the graph; thus, one of those two lines stabs $`k+1`$ edges, implying the claim. $`\mathrm{}`$

Our variable gadgets look as in Figure 7; shown is the gadget for variable $`x_i`$; note that the gadgets for $`x_0,\mathrm{},x_{i1}`$ are left and below the box spanned by the gadget, while the gadgets for $`x_{i+1},\mathrm{},x_{n1}`$ are above and to the right of the spanning box. The bold squares below the gadget indicate the position of literal gadgets, which wil be discussed further down.

Also note the use of vertical barrier gadgets: a number of $`i`$ next to it indicates a gadget consisting of $`3i`$ vertices, which alread requires a crossing number of $`i+1`$; thus, only $`ki`$ additional edges in a spanning tree may cross the dotted line induced by such a gadget. The arrows pointing down from the bottom indicate a number of literal gadgets, consisting of $`2\times 2`$ arrangements of vertices. See Figure 8 for the resulting overall arrangement.

###### Lemma 7

Let $`S`$ be the arrangement of vertices shown in Figure 7, with barrier gadgets placed and sized as indicated, and let $`PS`$. Let $`P`$ be constructed as shown in Figure 8. Then any spanning tree of $`P`$ that has stabbing number at most $`k+1`$ must use at least one of the two edges at the bottom of the arrangement, labeled $`e_t^{i,1}`$ (for *true*) or $`e_f^{i,1}`$ (for *false*.)

Proof. Assume there is a spanning tree of stabbing number at most $`k+1`$. Consider the barrier gadgets labeled $`B_1^i`$, $`B_2^i`$, $`B_3^i`$, $`B_4^i`$, and the corresponding lines, $`\mathrm{}_1^i`$, $`\mathrm{}_2^i`$, $`\mathrm{}_3^i`$, $`\mathrm{}_4^i`$. By the previous lemma, no edge can cross one of those lines. Therefore, the literal boxes below each clause must be connected within the vertical strips bounded by $`\mathrm{}_2^i`$ and $`\mathrm{}_3^i`$ on one hand, or $`\mathrm{}_3^i`$ and $`\mathrm{}_4^i`$, on the other hand. This requires at least one edge within each of the two strips to cross the line $`\mathrm{}_0^i`$. Moreover, the lines $`\mathrm{}_1^i`$ and $`\mathrm{}_4^i`$ must not be crossed, implying that the variable gadgets are connected to their neighbors at barriers $`B_1^i`$ and $`B_4^i`$. These connections between neighboring variable gadgets form a stair-like chain of variable gadgets, as shown in Figure 8: connections are in increasing $`x`$\- and $`y`$-order, which correspond to increasing variable indices; we call this the exterior stair. Similarly, the barrier gadgets associated with each of the two truth settings of a variable form one stair-like chain each, as shown in Figure 7; we call these the two interior stairs.

Now consider the horizontal barrier $`B_0^i`$, consisting of three groups of $`k52(n1i)`$ vertices each. By the previous arguments, the line $`\mathrm{}_0`$ has to cross all of the edges connecting the true and false literal boxes of the $`n1i`$ variables with higher indices, i.e., cross $`2(n1i)`$ edges. Furthermore in variable $`x_i`$ there are four other edges that connect vertices above line $`l_0^i`$ to vertices below $`l_0^i`$ and so are crossed by $`l_0^i`$. For example these edges could be the ones labeled $`c_1^i,c_2^i,c_3^i,c_4^i`$ in the figure. This allows only one of the edges $`e_t^{i,2}`$ and $`e_f^{i,2}`$ to be used for connecting the two interior stairs with each other and with the exterior stair; thus, at least one of the edges $`e_f^{i,1}`$ and $`e_t^{i,1}`$ must be used, proving the claim. $`\mathrm{}`$

Making use of the above gadgets, we get

###### Theorem 8

It is $`𝒩𝒫`$-hard to determine $`\text{St-Tre}_2(P)`$.

Proof. The basic idea for the construction is similar to the one used in the previous sections, making use of Lemmas 6 and 7. The use of gadgets and the overall layout of the construction are shown in Figure 8.

Given a Boolean expression $`B(x_0,x_1,\mathrm{},x_{n1})`$, we can find a vertex set that has a spanning tree of a stabbing number $`k+1`$, if and only if $`B`$ is satisfiable. Consider the vertex set as given in Figure 8 with $`k=3n`$. If $`B(x_0,x_1,\mathrm{},x_{n1})`$ has a satisfying truth assignment, we first connect the vertex on the left side of the drawing into one long path. This path contains all horizontal and vertical barrier gadgets as shown in Figure 8. We connect the variable and literal gadgets according to their values in $`B`$. In each *true*\- and *false*-column, there is a vertex lower than all horizontal barriers, and to the right of all literals in that column. We connect this vertex to the right lowest vertex of the lowest literal in the same column. Because each clause has at least one true literal, the horizontal stabbing number of a stabber through a clause is at most $`k`$, because the horizontal barrier on the left contributes $`k2n1`$, the variable(s) set to true and the $`n3`$ variables that do not appear in the clause contribute two each, and the variable(s) set to false contribute three each, which is at most $`k2n1+2(n2)+6=k+1`$. A horizontal stabber through the horizontal barrier in the $`i`$-th variable gadget stabs $`k52(n1i)+1`$ edges in the barrier, one more edge to the left of the barrier, four edges of the variable to the right of the gadget and two more for each of the $`ni`$ variables to its right, for a total of $`k52(n1i)+1+5+2(n1i)=k+1`$. A vertical stabber through literals stabs at most $`k1`$ edges in the vertical barriers, plus two more, either one from a false literal and one in the variable gadget, or two edges in the true literals. So we have a spanning tree of stabbing number $`k+1`$.

Conversely, assume that the vertex set has a spanning tree of stabbing number $`k+1`$. As we showed in the proof of Lemma 7, the literal gadgets can only be connected within their respective strips, forcing at least $`2n`$ stabbed edges. Furthermore, each *false* literal (being connected in a “u”-like fashion) causes an additional stabbed edge, while a *true* literal (connected in a “c”-like fashion) does not cause any additional stabbings. Thus, each clause must contain at least one *true* literal. Because of Lemma 7, at least one of the edges $`e_f^1`$ and $`e_t^1`$ must be present, guaranteeing that only the negated or only the unnegated literals for each variable can be connected in a “c”-like fashion, i.e., forcing a feasible setting of the variables. Thus, we get a truth setting of the variables that satisfies $`B`$. $`\mathrm{}`$

This immediately implies

###### Corollary 9

It is $`𝒩𝒫`$-hard to determine $`\text{St-Tre}(P)`$.

Proof. The argument is similar to the one in Corollary 3 for matchings: use the construction of Theorem 8, for which the criticality of certain axis-parallel lines requires satisfying a 3SAT instance in order to achieve low stabbing number. Scale down the bounding boxes for all gadgets, with literal gadgets ending up in appropriately smaller bounding boxes. Then perturb the position of the gadgets, shifting all vertices in the same gadget by the same amount, such that no line can intersect the bounding boxes of any three gadgets, again inserting a sufficient vertical distance for excluding a line that stabs a variable gadget and two of its literal gadgets. This leaves only the axis-parallel lines to be critical, implying the same combinatorial behavior as in the axis-parallel case. $`\mathrm{}`$

The hardness proof for minimizing the crossing number has the same structure as the one for stabbing number. Instead of the barrier gadget implied by Lemma 6, we use a slightly different one, as shown in Figure 9.

###### Lemma 10

Let $`S`$ be the $`k\times ((k1)^2+k)`$ arrangement of vertices shown in Figure 9, and let $`PS`$. If $`P`$ has a spanning tree $`T`$ with crossing number $`k`$, then no edge of $`T`$ connecting two vertices outside of the arrangement crosses the horizontal strip spanned by the arrangement.

Proof. Suppose there is a crossing edge. Consider the $`(k1)^2+k`$ horizontal lines that pass through $`k`$ vertices of the vertex arrangement. Because of the crossing edge, the intersection of each line with the edges and vertices within each corresponding horizontal set cannot consist of more than $`k1`$ connected components, so this intersection must contain at least one horizontal edge within the set; thus, a total of at least $`(k1)^2+k`$ horizontal edges within the arrangement cannot be avoided. Now consider the $`k`$ vertical lines that pass through $`(k1)^2+k`$ vertices of the arrangement; these lines subdivide the plane into $`k+1`$ vertical strips, $`k1`$ of which have width 1. Any of the at least $`(k1)^2+k`$ horizontal edges within the arrangement must cross at least one of the intermediate strips; thus, the average number of horizontal edges per bounded strip is at least $`\frac{(k1)^2+k}{k1}=(k1)+\frac{k}{k1}>k`$. By the pigeonhole principle, this implies that there must be a bounded vertical strip that is crossed by more than $`k`$ edges, a contradiction to our assumption that the crossing number is at most $`k`$. $`\mathrm{}`$

As the figure shows, there is a feasible subtree of the gadget, as long as no edge crosses the indicated strip. This allows us to use the arrangement as a barrier gadget. As for the rest of the construction for the proof of Theorem 8, stabbing and crossing numbers coincide, this immediately implies the following.

###### Theorem 11

It is $`𝒩𝒫`$-hard to determine $`\text{Cr-Tre}_2(P)`$.

From this it is easy to derive the following, again using a perturbation argument.

###### Corollary 12

It is $`𝒩𝒫`$-hard to determine $`\text{Cr-Tre}(P)`$.

Proof. The argument is similar to the one in Corollary 9: use perturbation to ensure that only axis-parallel lines can stab more than two gadgets. The only additional difficulty that has to be overcome is the fact that a diagonal line through one of the barrier gadgets in Figure 9 may have crossing number $`k`$: in principle, crossing number $`2k`$ could arise from stabbing two such gadgets in a non-axis-parallel manner. However, scaling the bounding boxes of the barrier gadgets in a way that the vertical dimension is much smaller than the horizontal dimension (say, by a factor of $`O(\epsilon ^{n^3})`$) makes sure that only lines of slope within range $`[\epsilon ^{n^3},\epsilon ^{n^3}]`$ achieve crossing number $`k`$ for one gadget. Thus, only almost horizonal lines are of concern; it is easy to see that the above perturbation guarantees that no such line intersects more than one barrier gadget. Therefore, only axis-parallel lines can be critical, and the hardness proof remains valid.

## 4 Integer Linear Programs for Minimum Stabbing Number

In view of the negative complexity results for our problems there are two major directions to proceed: providing (good) lower bounds on the minimum stabbing number in order to obtain approximation algorithms; and insisting on optimality despite $`𝒩𝒫`$-hardness. Our (integer) linear programming approach is an elegant way to combine both issues. We deal with them in the next two sections.

### 4.1 Perfect Matchings

In combinatorial optimization, $`P`$ corresponds to the vertex set of a straight-line embedded complete graph $`G=(P,E)`$; then a matching $`M`$ can be represented by its edge incidence vector $`x\{0,1\}^E`$, where $`x_{ij}=1`$ if $`ijM`$, and $`x_{ij}=0`$ otherwise. Using these variables we are able to state an integer linear program for finding a perfect matching of minimum stabbing number. For $`SP`$, denote by $`\delta (S)=\{ijEiS,jS\}`$ the *cut* induced by $`S`$.

minimize $`k`$ (1)
s.t. $`{\displaystyle \underset{ij\delta (\{i\})}{}}x_{ij}`$ $`=1`$ $`iP`$ (2)
$`{\displaystyle \underset{ij\delta (S)}{}}x_{ij}`$ $`1`$ $`\mathrm{}SP,|S|\text{ odd}`$ (3)
$`{\displaystyle \underset{ij:ij\mathrm{}(d)\mathrm{}}{}}x_{ij}`$ $`k`$ $`\text{ stabbing line }\mathrm{}(d)\text{ in direction }d`$ (4)
$`x_{ij}`$ $`\{0,1\}`$ $`ijE`$ (5)
We obtain the associated linear programming (LP) relaxation by replacing (5) by
$`x_{ij}`$ $`0`$ (5)
The inequalities (2) and (3) are necessarily satisfied for any perfect matching given by $`x`$, where the blossom constraints (3) ensure that any subset of vertices of odd cardinality has at least one edge to the outside. In his seminal paper Edmonds  showed that—together with (5)—these inequalities already constitute the complete description of the perfect matching polytope, that is, its extreme vertices exactly correspond to the incidence vectors of perfect matchings in $`G`$, i.e., the LP relaxation is integral.

To this description we add the stabbing constraints (4), for which we count the number of intersections of matching edges with any given line; this number is bounded by the variable $`k`$, and $`k`$ is minimized. We have to choose this way of modeling because of our min-max objective. An optimal solution $`x`$ to the integer program (1)–(5) represents a matching with stabbing number exactly $`\text{St-Mat}(P)`$. In a pure integer programming description, the blossom constraints are implied; however, Figure 10 shows that the introduction of stabbing constraints yields a polytope that is no longer integral, which is to be expected for an $`𝒩𝒫`$-hard problem. That is why we consider the LP relaxation, for which the use of blossom constraints yields a considerably tighter set of solutions. We will make use of this fact in the following section; here we comment on the complexity of the given LP and its solution.

We can limit the number of stabbing constraints (4): for the axis-parallel stabbing number, we can assume without loss of generality that a critical stabbing line runs through a vertex, so we get at most $`O(n)`$ restrictions for the axis-parallel stabbing number; for the general stabbing number, we may assume that a critical stabbing line runs through two vertices, so we can limit ourselves to $`O(n^2)`$ restrictions. On the other hand, we have exponentially many blossom inequalities; however, it is well known that blossom inequalities can be separated in polynomial time , i.e., one can check in polynomial time whether a given $`x`$ violates some blossom inequality, and if so, identify such an inequality. This polynomial-time *separation* allows us to solve the linear programming relaxation (1)–(5) in strongly polynomial time \[23, Thm. 5.11\] by means of the ellipsoid method \[14, Thm. 66.5\]. An optimal solution $`x`$ will in general be fractional, and we speak of *fractional stabbing number* in this context. It is a lower bound on $`\text{St-Mat}(P)`$.

### 4.2 Spanning Trees

There are several polynomial-size LP formulations for spanning trees, see e.g., . However, similar to matchings, we choose an exponential-size integer program that is again based on cut constraints. We directly state the LP relaxation.

minimize $`k`$ (6)
s.t. $`{\displaystyle \underset{ijE}{}}x_{ij}`$ $`=n1`$ (7)
$`{\displaystyle \underset{ij\delta (S)}{}}x_{ij}`$ $`1`$ $`\mathrm{}SP`$ (8)
$`{\displaystyle \underset{ij:ij\mathrm{}(d)\mathrm{}}{}}x_{ij}`$ $`k`$ $`\text{ stabbing line }\mathrm{}(d)\text{ in direction }d`$ (9)
$`x`$ $`0`$ (10)
Equation (7) ensures the right number of edges in a tree solution, and connectivity is given by the cut constraints (8). Just like blossom constraints for matching problems, separation over these constraints can be done in polynomial time by means of a minimum cut routine, so this LP can also be solved in strongly polynomial time.

## 5 Iterated Rounding

The above LP relaxations provide lower bounds for optimal solutions, but no upper bounds in the form of feasible solutions for our stabbing problems (except if we solve the integer programs, which may take exponential time). Therefore, our next objective is to find, in polynomial time, an integer solution that is not too far from an optimal one.

For this purpose we consider the *support graph* of a (fractional) solution $`x`$: it consists of all edges $`e`$ that have a strictly positive value $`x_e>0`$. If we could be assured that in any optimal LP solution, all edges $`e`$ in the support graph solution were $`b`$-heavy, i.e., $`x_eb`$ for some constant $`b>0`$, then we could consider rounding up all positive edge weights to one in order to get a $`1/b`$-approximation. Unfortunately, Figure 11 gives an indication that there may not be such a lower bound.

An alternative to simple LP rounding is offered by the iterated rounding technique introduced by Jain  for generalized Steiner network problems: at each step, it suffices to identify one heavy edge, round it up to one, fix it, and re-solve the remaining LP. The key ingredient is that the modified LP also has a heavy edge, so the process can be iterated, hence the name: *iterated rounding*.

A crucial step in Jain’s seminal work was the fact that for so-called generalized Steiner networks, $`1/2`$ is a valid lower bound for the value of the heaviest edge of fractional weight. A sufficient condition for the validity of this bound that is purely combinatorial is that all constraints in the LP relaxation are cut constraints, i.e., of type $`_{e\delta (S)}x_eb(S)`$.

Unfortunately, stabbing constraints do not fall into the category of cut constraints, and it can be seen from Figure 10 that Jain’s lower bound does not hold for stabbing problems. This makes it necessary to establish a separate lower bound on the value of the heaviest fractional edge. We will do this by exploiting the underlying geometric nature of our optimization problem, and establish the fact that there always is an optimal LP solution with planar support graph. Planarity is proven by shifting weight from a crossing pair of edges to a non-crossing one; for matchings (Lemma 13) this requires some extra care because of the blossom inequalities. The proof for spanning trees (Lemma 14) is almost completely analogous.

###### Lemma 13

For any even set of vertices in the plane, there is a fractional perfect matching $`x`$ of minimum stabbing number, such that the support graph of $`x`$ is planar. Such a fractional matching can be found in polynomial time.

Proof. The set of all LP solutions is bounded and nonempty, so the set of all optimal solutions is nonempty and compact. From this set, consider a solution $`x`$ that minimizes the total stabbing number, i.e., the sum of stabbing numbers over all combinatorially different lines. We claim that the support graph of $`x`$ cannot contain any crossing pair of edges. Refer to Figure 12.

Suppose there were $`e_{13}:=\{v_1,v_3\}`$, $`e_{24}:=\{v_2,v_4\}`$ with $`x_{e_{13}}>0`$ and $`x_{e_{24}}>0`$, such that $`e_{13}`$ and $`e_{24}`$ cross. We will argue that this implies the existence of an alternative solution of the same maximum stabbing number, but infinitesimally smaller total stabbing number, i.e., a contradiction to our assumptions on optimality.

Consider $`e_{12}:=\{v_1,v_2\}`$, $`e_{34}:=\{v_3,v_4\}`$, $`e_{14}:=\{v_1,v_4\}`$, $`e_{23}:=\{v_2,v_3\}`$. Among all LP constraints (1)–(5), let $`s(x)`$ be the smallest positive slack (i.e., difference between left-hand and right-hand side), and choose $`0<\epsilon <s(x)`$. As $`_{e\delta (v_i)}x_e=1`$ and $`x_{e_{13}}>\epsilon `$, $`x_{e_{24}}>\epsilon `$, we have $`x_{e_{12}}<1\epsilon `$, $`x_{e_{34}}<1\epsilon `$, $`x_{e_{14}}<1\epsilon `$, $`x_{e_{23}}<1\epsilon `$.

Consider two possible alternative solutions arising from shifting an $`\epsilon `$ of weight from $`e_{13}`$ and $`e_{24}`$. Let $`x^{}`$ and $`x^{\prime \prime }`$ be defined by

$$x_e^{}:=\{\begin{array}{ccc}x_e\epsilon & \text{ for }& e\{e_{13},e_{24}\},\\ x_e+\epsilon & \text{ for }& e\{e_{12},e_{34}\}\\ x_e& \text{ for }& \text{ all other }e,\end{array}$$
(11)
and

$$x_e^{\prime \prime }:=\{\begin{array}{ccc}x_e\epsilon & \text{ for }& e\{e_{13},e_{24}\},\\ x_e+\epsilon & \text{ for }& e\{e_{14},e_{23}\},\\ x_e& \text{ for }& \text{ all other }e.\end{array}$$
(12)
By convexity, both $`x^{}`$ and $`x^{\prime \prime }`$ satisfy all stabbing constraints that are valid for $`x`$. Furthermore, it is easy to see that both $`x^{}`$ and $`x^{\prime \prime }`$ have smaller total stabbing number than $`x`$. Thus, it suffices to argue that at least one of these solutions satisfies all blossom inequalities.

Assume that for each of the two alternative solutions, a blossom inequality is violated; by our assumption on $`\epsilon `$, this means that there are two odd sets, $`S_1P`$ and $`S_2P`$, such that $`_{e\delta (S_1)}x^{}(e)<1`$ and $`_{e\delta (S_2)}x^{\prime \prime }(e)<1`$, while $`_{e\delta (S_1)}x_e=1`$ and $`_{e\delta (S_2)}x_e=1`$. Let $`s_i:=|\{v_1,v_2,v_3,v_4\}S_i|`$. It is straightforward to see that for $`s_i\{0,1,3,4\}`$, both $`x^{}`$ and $`x^{\prime \prime }`$ satisfy all blossom inequalities that are valid for $`x`$; similarly, the blossom inequalities are satisfied for $`v_1,v_3S_1`$ and $`v_2,v_4\overline{S_1}`$, as $`_{e\delta (S_1)}x^{}(e)>_{e\delta (S_1)}x(e)`$. Therefore, we only need to consider $`v_1,v_2S_1`$ and $`v_3,v_4\overline{S_1}`$, and $`v_1,v_4S_2`$ and $`v_2,v_3\overline{S_2}`$. Let $`T_1:=S_1S_2`$, $`T_2:=S_1\overline{S_2}`$, $`T_3:=\overline{S_1}\overline{S_2}`$ $`T_4:=\overline{S_1}S_2`$, and $`E_{ij}:=\{e=\{x,y\}ExT_i,yT_j\}`$. As $`|T_1T_2|`$, $`|T_1T_4|`$, $`|T_2T_3|`$, and $`|T_3T_4|`$ are all odd, we may assume without loss of generality that $`|T_1|`$ and $`|T_3|`$ are odd, and $`|T_2|`$ and $`|T_4|`$ are even.

Then we have

$`2`$ $`=`$ $`{\displaystyle \underset{e\delta (S_1)}{}}x_e+{\displaystyle \underset{e\delta (S_2)}{}}x_e`$ (13)
$`=`$ $`{\displaystyle \underset{e\delta (T_1)}{}}x_e+{\displaystyle \underset{e\delta (T_3)}{}}x_e+2{\displaystyle \underset{eE_{24}}{}}x_e`$ (14)
$``$ $`{\displaystyle \underset{e\delta (T_1)}{}}x_e+{\displaystyle \underset{e\delta (T_3)}{}}x_e+2x_{e_{24}}`$ (15)
$`>`$ $`{\displaystyle \underset{e\delta (T_1)}{}}x_e+{\displaystyle \underset{e\delta (T_3)}{}}x_e.`$ (16)
This implies that $`\mathrm{min}\{_{e\delta (T_1)}x_e,_{e\delta (T_3)}x_e\}<1`$, contradicting the assumption that $`x`$ satisfies all cut inequalities. $`\mathrm{}`$

The above lemma establishes the existence of optimal non-crossing matchings; when actually trying to find a non-crossing matching, it suffices to consider an additional term in the objective function of our LP that refers to the total length of the edges. This ensures that the total length of matching edges is minimized, avoiding crossings in the first place. For more details, see our experimental paper .

For the case of spanning trees, we can use a similar approach, based on a similar lemma.

###### Lemma 14

For any set of vertices in the plane, there is a fractional spanning tree $`x`$ of minimum stabbing number, such that the support graph of $`x`$ is planar. Such a fractional spanning tree can be found in polynomial time.

Proof. We proceed completely analogous to the proof of the previous lemma to deduce that if there was a fractional solution $`x`$ of minimum total stabbing number among all solutions with optimal stabbing number, such that the support graph of $`x`$ has two crossing edges, then we could shift an infinitesimal amount of weight from the crossing edges to two non-crossing ones, such that the stabbing number remains the same, but the total stabbing number decreases.

The technical steps of the argument are virtually identical: consider two crossing edges $`e_{13}`$ and $`e_{24}`$ as shown in Figure 12, and the alternative solutions $`x_e^{}`$ and $`x_e^{\prime \prime }`$ as defined in (11) and (12). For arguing that at least one of these solutions is feasible, we do not have to consider blossom constraints, but cut constraints of type (8).

Assume that for each of the two alternative solutions, a cut constraint is violated; by our assumption on $`\epsilon `$, this means that there are two sets, $`S_1P`$ and $`S_2P`$, such that $`_{e\delta (S_1)}x^{}(e)<1`$ and $`_{e\delta (S_2)}x^{\prime \prime }(e)<1`$, while $`_{e\delta (S_1)}x_e=1`$ and $`_{e\delta (S_2)}x_e=1`$. Let $`s_i:=|\{v_1,v_2,v_3,v_4\}S_i|`$. It is straightforward to see that for $`s_i\{0,1,3,4\}`$, both $`x^{}`$ and $`x^{\prime \prime }`$ satisfy all cut inequalities that are valid for $`x`$; similarly, the cut inequalities are satisfied for $`v_1,v_3S_1`$ and $`v_2,v_4\overline{S_1}`$, as $`_{e\delta (S_1)}x^{}(e)>_{e\delta (S_1)}x(e)`$. Therefore, we only need to consider $`v_1,v_2S_1`$ and $`v_3,v_4\overline{S_1}`$, and $`v_1,v_4S_2`$ and $`v_2,v_3\overline{S_2}`$. Let $`T_1:=S_1S_2`$, $`T_2:=S_1\overline{S_2}`$, $`T_3:=\overline{S_1}\overline{S_2}`$ $`T_4:=\overline{S_1}S_2`$, and $`E_{ij}:=\{e=\{x,y\}ExT_i,yT_j\}`$. Using a sequence of estimates that is completely identical to (13)–(16), we get $`2>_{e\delta (T_1)}x_e+_{e\delta (T_3)}x_e,`$ again implying that $`\mathrm{min}\{_{e\delta (T_1)}x_e,_{e\delta (T_3)}x_e\}<1`$, contradicting the assumption that $`x`$ satisfies all blossom inequalities. $`\mathrm{}`$

###### Theorem 15

For any even set of vertices in the plane, there is a fractional perfect matching $`x`$ of minimum stabbing number that has an edge of weight at least $`1/5`$. For any set of vertices in the plane, there is a fractional spanning tree $`x`$ of minimum stabbing number that has an edge of weight more than $`1/3`$.

Proof. For both problems, consider a fractional vertex with a planar support graph. To see the claim for matchings, note that there must be a vertex with degree at most five; as the total weight for each vertex is 1, the claim follows. To see the claim for spanning trees, note that the total edge weight is $`n1`$, and the number of edges is at most $`3n6`$, implying that the average weight is larger than $`1/3`$. $`\mathrm{}`$

Theorem 15 provides the basic ingredient for an iterated rounding algorithm: at each iteration, fix the weight of an edge of maximum fractional weight to one, and re-solve the linear program. In each iteration, the number of edges with fractional weight is reduced, so we get an overall polynomial-time algorithm for finding an integral solution.

Unfortunately, Jain’s original proof only guarantees a constant-factor approximation for objective functions that arise as the (weighted) sum of the edge variables. However, the situation is different for our objective function which is a *maximum* over certain sums of edge variables, so an additional argument is needed for establishing a constant-factor guarantee. We are hopeful that this argument can be completed some time in the future . As we demonstrate in our experimental paper , the practical performance seems to be even better than the theoretically possible guarantees of 5 and 3.

## 6 Notes and Conclusion

We have presented the first algorithmic paper on stabbing numbers, resolving the long-standing open question of complexity, and providing an approach that appears to be useful in theory and in practice. There are a number of interesting open questions.

Our proofs rely on a strong degeneracy of the vertex set, and it would be interesting to see a proof for vertices in general position.

We were not able to extend our $`𝒩𝒫`$-hardness proof to the case of finding a triangulation of minimum general crossing number; another interesting issue is how to convert the $`𝒩𝒫`$-hardness proof for triangulations of minimum crossing number into an $`𝒩𝒫`$-hardness proof for minimum stabbing number.

Probably the most intriguing open question spawned by our work is whether the iterated rounding scheme suggested by the existence of a heavy edge in an optimal fractional solution to our linear programs (Lemmas 13 and 14) does indeed lead to a constant-factor approximation algorithm. Also, the use of the ellipsoid method (at least as a theoretical argument) is not “combinatorial,” which always has to be considered a drawback.

Another interesting question is to decide the existence of structures of small constant stabbing number. As the hardness proof for deciding the existence of a matching of stabbing number 5 illustrates, this is still not an easy task. From some solvable special cases, we only note one; for a proof, see .

###### Theorem 16

$`\text{St-Tre}_2(P)`$=2 and $`\text{St-Mat}(P)`$=2 can be decided in polynomial time.

One may also ask for minimizing the average instead of the maximum stabbing number, and refer to the average over the whole continuum of lines intersecting a set of line segments, instead of just a combinatorial set of representatives. This, however, amounts to solving problems of minimum length, with all implications to hardness and approximation; again, see  for details.

###### Theorem 17

A set of line segments has minimum average (axis-parallel, resp.) stabbing number with respect to uniform distribution of lines, if and only if the overall Euclidean (Manhattan, resp.) length of all line segments is minimum.

We remark that a linear program for minimizing the average stabbing number can be written with a sum in the objective function (instead of a maximum as we had to model it), allowing us to directly apply our iterated rounding technique and obtaining the desired approximation factors of 3 and 5, respectively; see .

## Acknowledgments

We thank Joe Mitchell for pushing us to work on this problem, and repeated discussions that assured further progress. We also thank Kamal Jain for some discussions on iterated rounding. We are greatly indebted to two anonymous referees, who put in many hours of work in going through all the details of this paper, providing an amazing number of helpful hints, and greatly improving clarity and accessibility of this paper.


format: text

text:
# Complex Energy Method in four Body Faddeev-Yakubovsky Equations

## Acknowlegements

Authors would like to thank Prof. W. Glöckle for helping us to read this manuscript carefully. The calculations are performed on SX-5/128M8 (Research Center for Nuclear Physics), SX-5/6B (National Institute for Fusion Science), HP X4000 (Frontier Research Center for Computational Science, Tokyo University of Science) in Japan, and partly on Hitachi SR8000 (Leibnitz-Rechenzentrum für die Münchener Hochschule) in Germany.


text:
# Evidence for an incommensurate magnetic resonance in La2-xSrxCuO4

## I Introduction

It has been observed in a variety of cuprate superconductorsRegnault et al. (1995); Dai et al. (2001); Fong et al. (1999); Mesot et al. (2000); He et al. (2002) that the inelastic magnetic scattering is enhanced below the superconducting transition temperature, $`T_c`$, at a particular energy, $`E_r`$, commonly referred to as the magnetic resonance energy. The “resonant” magnetic scattering is found to be centered at the antiferromagnetic wave vector and to have a rather narrow width in energy. The ratio $`E_r/kT_c`$ is observed to be in the range of 5 to 6.

One apparently anomalous system is La2-xSrxCuO4. To the best of our knowledge,Kastner et al. (1998) no one has identified a commensurate “resonant” response in this system by neutron scattering; nevertheless, when certain theoretical interpretations of the optical conductivitySchachinger and Carbotte (2000) and angle-resolved photoemissionEschrig and Norman (2000) are applied to measurements on La2-xSrxCuO4,Singley et al. (2001); Zhou et al. (2003) they seem to imply a resonance at an energy of roughly 40 meV. On the other hand, Mason and coworkersMason et al. (1996); Lake et al. (1999) found, for samples near optimum doping, an enhancement of magnetic scattering below $`T_c`$ at incommensurate wave vectors and occurring for energies centered at about 9 meV. A concommitant narrowing in q width was also observed. It seems possible that this effect corresponds to the commensurate resonance seen in other cuprates.

To test the connection with the resonance phenomenon, it is desirable to perform further characterizations. One signature of the resonant magnetic scattering in underdoped YBa2Cu3O6+x is that the resonant scattering is reduced in amplitude by application of a uniform magnetic field.Dai et al. (2000) Here we study the effect of a field on the incommensurate scattering in a slightly overdoped crystal of La1.82Sr0.18CuO4. We find that, below $`T_c`$, the applied field reduces the peak intensity of the incommensurate scattering at 9 meV, thus providing support for associating the enhanced incommensurate scattering with the commensurate resonance response found in other cuprates.

There has also been considerable recent interest in the impact of an applied field on magnetic scattering at lower energies. In particular, an applied field has been found to enhance elastic incommensurate scattering in underdoped samples,Katano et al. (2000); Lake et al. (2002); Khaykovich et al. (2002, 2003) and to induce inelastic scattering within the spin gap of an optimally doped sample.Lake et al. (2001) For our slightly overdoped sample, it appears that the field causes weight to shift into the gap from higher energy, causing the frequency dependence to become more like that of the normal state just above $`T_c`$. These results are compared with a recent studyKimura et al. (2003) of Zn-doped La1.85Sr0.15CuO4.

## II Experimental Details

The experiment was performed on triple-axis spectrometer IN22 at the Institute Laue Langevin, which is equipped with a vertically-focusing monochromator and a double-focusing analyzer of pyrolytic graphite, using the (002) reflection. No collimators were used, but cadmium masks were placed as close as possible to the sample (just outside of the magnet) to limit the beam size. We worked in fixed-$`E_f`$ mode, with $`k_f=2.662`$ Å-1 and a PG filter after the sample.

The sample was an array of four crystals grown at Kyoto University, and co-aligned in an aluminum holder. The total crystal volume was approximately 1.5 cm3. Magnetic susceptibility measurements indicated that $`T_c37`$ K. These crystals are similar to, but distinct from, a sample of the same composition used in recent study of the spin gap.Lee et al. (2003) For the present sample, the tetragonal-to-orthorhombic structural transition is at 118 K, whereas the transition is at 111 K for the previous sample. The higher transition temperature corresponds to a slightly lower Sr content.

The crystals, oriented with the  direction vertical, were mounted in a 12-T split-coil, vertical-field magnet. Thus, the applied field was along the $`c`$-axis, and we could study scattering within the $`(hk0)`$ zone. (The  direction was aligned in the horizontal scattering plane, but the  direction was tilted out of plane by $`2^{}`$.) We made use of an orthorhombic unit cell with $`ab=5.316`$ Å.

For scans as a function of energy at fixed Q, we should, in principle, correct the intensities for energy-dependent counting-time errors due to the presence of harmonics in the beam that reaches the incident-beam monitor (see Chap. 4, Sec. 9, in Ref. Shirane et al., 2002). A correction factor is known for instruments at the reactor face; however, IN22 is at the end of a thermal guide, which should reduce the relative intensities of harmonics. As we have not measured the harmonic content of the incident beam, we are not able to make the proper correction (which, at most, would involve a 20% effect over the measured energy range). This situation will have no impact on the conclusions of our analysis, which focuses on the variations of the inelastic signal with temperature and applied field; however, this effect, together with the coarser resolution used here, could be responsible for minor differences from the previous study.Lee et al. (2003)

## III Results

The low-energy magnetic scattering in La1.82Sr0.18CuO4 is characterized by peaks at four incommensurate points about the antiferromagnetic wave vector, $`𝐐_{\mathrm{AF}}`$. For a CuO2 layer with a square lattice, these peaks would be indexed as $`(\frac{1}{2}\pm \delta ,\frac{1}{2})`$ and $`(\frac{1}{2},\frac{1}{2}\pm \delta )`$, with $`\delta =0.13`$. In the orthorhombic unit cell which we will use in this paper, the coordinates are rotated by 45, becoming $`𝐐_\delta =(1+\delta ,\pm \delta )`$ and $`𝐐_\delta ^{}=(1\delta ,\pm \delta )`$, as shown in Fig. 1. Because of time constraints, most of the measurements involved measuring the scattered intensity at the two peak positions $`𝐐_\delta `$ and at background positions, $`𝐐_\mathrm{b}=(1+\delta ,\pm 0.4)`$ and $`𝐐_0=(1+\delta ,0)`$, with a typical counting time of 15 min per point. (The actual measurements were done with $`\delta =0.12`$, rather than 0.13; the difference is not significant for these measurements.) The background measurements were found to be essentially independent of field, but slightly temperature dependent (and, of course, energy dependent). To improve the statistics, the background measurements at each energy were fit to a simple, monotonic function of temperature. To obtain the net intensity at $`𝐐_\delta `$, the fitted background was subtracted from the average of the measurements at the two peak positions.

Figure 2 shows the energy dependence of the imaginary part of the dynamic susceptibility, $`\chi ^{\prime \prime }`$, at $`𝐐_\delta `$ measured at temperatures of 3 K and 38 K for zero field and $`H=10`$ T. $`\chi ^{\prime \prime }`$ was obtained by multiplying the net intensity by $`1\mathrm{exp}(\mathrm{}\omega /kT)`$. At $`TT_c`$ \[Fig. 2(a)\], the differences in $`\chi ^{\prime \prime }`$ with and without a field are small, and probably due to statistics. The line through the data points corresponds to

$$\chi _0^{\prime \prime }=A_0\frac{\mathrm{}\omega \mathrm{\Gamma }}{(\mathrm{}\omega )^2+\mathrm{\Gamma }^2},$$
(1)
with $`\mathrm{\Gamma }=9`$ meV.

At $`TT_c`$, Fig. 2(b), we see a definite systematic difference between zero field and 10-T measurements. Applying the field tends to introduce signal within the gap, and to decrease the signal above the gap. The solid curve through the zero-field data corresponds to the phenomenological form

$$\chi _{\mathrm{sc}}^{\prime \prime }=A_1\chi _0^{\prime \prime }[F_+(\omega )+F_{}(\omega )]\left(\frac{\mathrm{\Delta }_s}{\mathrm{}\omega }\right)^2,$$
(2)
where $`\chi _0^{\prime \prime }`$ (dot-dashed line) is from Eq. (1) and

$$F_\pm (\omega )=\mathrm{tanh}\left(\frac{\mathrm{}\omega \pm \mathrm{\Delta }_s}{\gamma }\right),$$
(3)
with $`\mathrm{\Delta }_s=8`$ meV, $`\gamma =1.5`$ meV, and $`A_1=1.5`$. The dashed curve, which roughly describes the in-field data, is given by

$$\chi ^{\prime \prime }=0.5\chi _{\mathrm{sc}}^{\prime \prime }+0.5\chi _0^{\prime \prime },$$
(4)
where $`\chi _0^{\prime \prime }`$ corresponds to the curve in Fig. 2(a) at 38 K. The curves are intended to be suggestive guides to the eye, rather than perfect fits to the data.

The temperature dependence of $`\chi ^{\prime \prime }`$ at 3 meV and 9 meV is shown in Fig. 3. At 3 meV, the in-field data are systematically finite and higher than the zero-field data for $`T<T_c`$. At 9 meV, the in-field signal is reduced compared to zero-field. The curves are intended as suggestive guides to the eye, using a BCS-like function, $`\sqrt{1(T/T_c)^4}`$. In zero field, the measured $`T_c`$ is 37 K (solid lines), while for $`H=10`$ T, we estimate $`T_c=27`$ K from the magnetization study of Li et al.Li et al. (1993)

In their study of field effects on underdoped YBa2Cu3O6+x, Dai et al.Dai et al. (2000) argued that the resonant response is a measure of superconducting coherence. The onset of coherent superconductivity is reduced by the applied field, so that one would expect the onset of 9-meV signal enhancement and 3-meV signal reduction to follow $`T_c(H)`$. Our measurements seem to be consistent with such a scenario; however, there are insufficient data points at higher temperatures and the error bars are too large to allow one to draw any firm conclusions regarding a quantitative correlation with $`T_c(H)`$.

Figure 4 shows constant-energy scans along $`𝐐=(1+\delta ,k)`$ (see dashed line in Fig. 1) for $`\mathrm{}\omega =3`$ meV on the left and 9 meV on the right, all measured at $`T=3`$ K. The 3-meV scans have a strongly q-dependent background contribution that makes it difficult to analyze the raw data. It is more practical to look at the difference (high field $``$ zero field), shown in (b). The difference is consistent with a symmetric pair of broad peaks at $`k=\pm 0.12(2)`$. The peak amplitude of 19(3)/3000 monitor counts is consistent with the results in Fig. 2(a) and Fig. 3(b) (see the vertical bar in the latter), thus confirming the growth of low-energy incommensurate scattering due to the presence of the field.

The 9-meV scans appear to have a more uniform background. The curves represent fits with symmetric Gaussian peaks. In zero field, the peaks are at $`k=\pm 0.134(3)`$ with amplitude $`=80(4)`$ and FWHM $`=0.148(7)`$; in 10 T the fit gives $`k=\pm 0.131(5)`$, amplitude $`=61(4)`$, and FWHM $`=0.183(10)`$. Applying the field broadens the peaks and reduces the amplitude; the amplitude change is consistent with Figs. 2 and 3(a) (see the filled symbols the latter).

In their study of La1.86Sr0.14CuO4, Mason et al.Mason et al. (1996) observed at 9 meV an enhancement of intensity and a narrowing in q when cooling through $`T_c`$, which they discussed as a coherence effect associated with superconductivity. We find that application of a 10-T field has the opposite effect: the magnetic susceptibility is reduced, and the $`q`$-width is increased. Again, this seems to be consistent with a reduction in superconducting coherence due to the field.

## IV Discussion

### IV.1 Resonance feature

In our slightly overdoped sample, we find that application of a uniform magnetic field parallel to the $`c`$ axis causes a reduction of $`\chi ^{\prime \prime }`$ at the energy of the peak ($`9`$ meV). The signal at this energy is otherwise enhanced on cooling below $`T_c`$. This behavior is reminiscent of the field-induced decrease in the resonance peak observedDai et al. (2000) in underdoped YBa2Cu3O6+x, the main difference being that the response occurs at an incommensurate, rather than commensurate, wave vector in La2-xSrxCuO4. We note that in the original analysis of the zero-field enhancement of the incommensurate signal, Mason et al.Mason et al. (1996) suggested that the increase in signal below $`T_c`$ came from the superposition of an extra contribution that is very narrow in $`q`$. Lacking a physical motivation for such a decomposition of the excitations, we believe it is more reasonable to view the changes below $`T_c`$ as a modification of the excitations that exist in the normal state.

In terms of the relative energy scale, the ratio $`E_r/kT_c`$ observed for other cupratesRegnault et al. (1995); Dai et al. (2001); Fong et al. (1999); Mesot et al. (2000); He et al. (2002) is found to lie in the range of 5–6, as mentioned in the introduction. If we identify $`E_r9`$ meV for our sample, then $`E_r/kT_c3`$. Relative to $`\mathrm{\Delta }_0`$, the maximum of the superconducting energy gap, $`E_r`$ is observed to always be less than $`2\mathrm{\Delta }_0`$, and generally not much greater than $`\mathrm{\Delta }_0`$. For La2-xSrxCuO4 with $`x=0.18`$, $`\mathrm{\Delta }_010`$ meV, based on tunnelingMomono et al. (1998) and Raman scattering studies,Chen et al. (1994) so $`E_r/\mathrm{\Delta }_0`$ is consistent with that for other systems.

Regarding energy scales, it is interesting to note that in a study of YBa2Cu3O6+x with $`x=0.51`$ and $`T_c=47`$ K, Rossat-Mignod et al.Rossat-Mignod et al. (1991) observed a spin gap of $`4`$ meV in the superconducting state together with an enhancement of $`\chi ^{\prime \prime }`$ (with respect to the normal state) peaked at $`7`$ meV. These energies are comparable to those in our La2-xSrxCuO4 sample. In more highly doped YBa2Cu3O6+x, where the attention has tended to focus on the commensurate resonance feature, we note that enhancements of $`\chi ^{\prime \prime }`$ at incommensurate wave vectors (for $`EE_r`$) have also been observed.Bourges et al. (2000); Dai et al. (1998); Reznik et al. (2003)

There has been a variety of theoretical approaches to the magnetic resonance and its energy and $`q`$ dependence. From the perspective of SO(5) theory, a model in which commensurate antiferromagnetism competes with $`d`$-wave superconductivity, a magnetic resonance is predicted to appear precisely at $`𝐐_{\mathrm{AF}}`$.Demler and Zhang (1995); Zhang (1997) It corresponds to a collective mode in the particle-particle channel, to which neutrons cannot couple except in the superconducting state where coupling is enabled by the coherent mixture of particles and holes in the BCS condensate. While the theory has been extended to include (nontopological) stripesVeillette et al. (1999) and dispersion of the resonance,Hu and Zhang (2001) the commensurate resonance appears to remain a central feature.

One alternative is to attribute the resonance to an excitation of antiferromagnetically-coupled Cu spins.Morr and Pines (1998); Abanov and Chubukov (1999) In the normal state, interactions with the charge carriers cause the spin fluctuations to be strongly damped, while fluctuations with energies below $`2\mathrm{\Delta }_0`$ become underdamped in the superconducting state. Since the $`q`$ dependence of the spin fluctuations is generally chosen to match experiment in this approach, it can be either commensurateMorr and Pines (1998); Abanov and Chubukov (1999) or incommensurate.Morr and Pines (2000)

The most common approach is to calculate the magnetic response of the charge carriers themselves in the particle-hole channel, which is then enhanced with the random phase approximation.Lavagna and Stemmann (1994); Mazin and Yakovenko (1995); Bulut and Scalapino (1996); Dahm et al. (1998); Brinckmann and Lee (1999); Kao et al. (2000); Onufrieva and Pfeuty (2002) Whether the calculated fluctuations are commensurate or incommensurate depends on the shape of the Fermi surface.Dahm et al. (1998); Kao et al. (2000); Norman (2000) Using a model dispersion that gives a Fermi surface consistent with the results of angle-resolved photoemission spectroscopy (ARPES) for YBa2Cu3O6+x and Bi2Sr2CaCu2O8+δ yields a commensurate resonance peak.Norman (2000)

CalculationsDahm et al. (1998); Kao et al. (2000) for La2-xSrxCuO4 have generally used parameters that give a Fermi surface that is closed about $`𝐤=0`$, rather than about $`𝐤=𝐐_{\mathrm{AF}}`$ as in the bilayer cuprates; however, it has been arguedKao et al. (2000) that the differences in models are not essential for obtaining the normal-state incommensurate structure in $`\chi ^{\prime \prime }`$. (We note that recent ARPES studies indicate that the Fermi surface for optimally doped La2-xSrxCuO4 is actually quite similar to that for the bilayer cuprates.Damascelli et al. (2003)) In any case, a commensurate resonance feature is predictedDahm et al. (1998); Kao et al. (2000) to appear below $`T_c`$; in particular, Kao et al.Kao et al. (2000) predict the resonance peak to occur at 15 meV. While we must admit that we have not pushed our measurements quite this high in energy, the maximum at 9 meV observed at an incommensurate wave vector does not appear to be consistent with these calculations.

Some theorists have argued that there is a connection between the magnetic resonance peak and certain anomalous features seen in ARPES measurements, such as the “peak-dip-hump” structureAbanov and Chubukov (1999); Eschrig and Norman (2000); Borisenko et al. (2003) and the “kink” in the quasiparticle dispersion.Eschrig and Norman (2000); Johnson et al. (2001) Eliashberg theory has been used to make a connection between the resonance and certain features in the optical conductivity.Schachinger and Carbotte (2000) (Theoretical arguments against such connections have also been made.Kee et al. (2002)) Now, it happens that the same anomalous “kink” and optical conductivity features identified for Bi2Sr2CaCu2O8+δ are also observed for La2-xSrxCuO4.Zhou et al. (2003); Singley et al. (2001) To consistently interpret these features in terms of the magnetic resonance, one would have to infer a commensurate resonance at an energy of about 40 meV for La2-xSrxCuO4. Our identification of the incommensurate 9-meV feature as the analog of the resonant mode contradicts such an inference.

Finally, we note that the low-energy magnetic excitations in the normal state of La2-xSrxCuO4 look very much like those observedTranquada et al. (1999); Ito et al. (2003) in stripe-ordered La1.48Nd0.4Sr0.12CuO4. In the latter system, one interprets the incommensurate excitations as spin waves of the magnetically ordered system. The differences for La2-xSrxCuO4 can be understood in terms of the fluctuations of a quantum-disordered systemChubukov et al. (1994) with stripe correlations.Kivelson et al.  The magnetic excitations are certainly sensitive to the charge fluctuations; after all, from the stripe perspective, the incommensurability is the direct result of the spatially inhomogeneous distribution of the doped holes.Zaanen and Gunnarsson (1989); Machida (1989); Emery et al. (1999) The generation of a spin gap, together with pairing of charge carriers, has been predicted based on a model that assumes the existence of stripes.Emery et al. (1997) One certainly expects singlet-triplet excitations to appear above the spin gap.Chubukov et al. (1994) A model for the magnetic resonance based on incommensurate spin waves has been proposedBatista et al. (2001); however, a naive comparison with spin-wave measurements in a stripe-ordered nickelate indicate that this model has some shortcomings.Bourges et al. (2003)

### IV.2 Field-induced signal in the spin gap

Neutron scattering experiments on underdoped La2-xSrxCuO4 (Refs. Katano et al., 2000; Lake et al., 2002) and on La2CuO4+δ (Refs. Khaykovich et al., 2002, 2003) have shown that application of a magnetic field along the $`c`$ axis at temperatures less than $`T_c`$ can induce or enhance spin-density-wave order. While there have been a number of proposals for the induced correlations in magnetic vortex cores, Arovas et al. (1997); Franz et al. (2002); Chen and Ting (2002); Lee and Wen (2001) we believe that the most natural explanation involves the pinning of charge and spin stripes by vortices.Zhang et al. (2002); Polkovnikov et al. (2002); Kivelson et al. (2002); Zhu et al. (2002); Chen et al. (2002); Takigawa et al. (2003); Andersen et al. (2003); Kivelson et al.  The observation that well developed charge and spin stripe order in La1.45Nd0.4Sr0.15CuO4 is not affected by application of a magnetic field is consistent with this picture.Wakimoto et al. (2003)

In contrast to the underdoped regime, there is a spin-gap in the superconducting state for optimally-doped La2-xSrxCuO4.Yamada et al. (1995); Petit et al. (1997); Lake et al. (1999) The gap in the low-energy spin fluctuations indicates that the spin stripes are further away from the ordered state,Polkovnikov et al. (2002); Kivelson et al. (2002, ) so it is not surprising that an applied magnetic field does not induce static correlations. Instead, Lake et al.Lake et al. (2001) showed, on a sample with $`x=0.163`$, that applying a field induces a signal within the spin gap. Our results are generally consistent with theirs. One difference is that they observed an upturn in the low-energy (2.5 meV) in-field signal as the temperature decreased below $`10`$ K, whereas we did not see such an upturn in our slightly overdoped sample.

The application of the magnetic field in the superconducting state introduces inhomogeneity associated with the vortices. The superconducting order parameter goes to zero at the center of each vortex, and the area over which the order parameter is strongly depressed is equal to $`\pi \xi ^2`$, where $`\xi `$ is the superconducting coherence length. The areal fraction corresponding to the vortex cores is equal to $`H/H_{c2}`$, where $`H_{c2}`$ is the field at which the sample becomes completely filled by vortex cores. The resistivity studies of Ando et al.Ando et al. (1999) indicate an $`H_{c2}`$ of approximately 55 T at 3 K for La2-xSrxCuO4 with $`x=0.17`$, while the Nernst effect study of Wang et al.Wang et al. (2002) suggests a low-temperature $`H_{c2}`$ of greater than 45 T for an $`x=0.20`$ sample. Taking $`H_{c2}50`$ T for our $`x=0.18`$ sample at 3 K, we find that, for our applied field of 10 T, $`H/H_{c2}0.2`$. Thus, 20% of the area is occupied by vortex cores.

We expect that the magnetic scattering associated with the vortex cores will be different from that due to the superconducting regions outside of the cores. We have seen that applying the magnetic field at 3 K causes $`\chi ^{\prime \prime }`$ to change so that it appears closer to the normal state. At 10 T, the measurements can be roughly modeled as an average between normal-state and zero-field-superconductor signals. If the normal state response came from just the vortex cores, then we would expect its weight to be just 20% instead of 50%. The larger normal-state response indicates that it must come from regions about 2.5 times the area of the vortex cores. This result is consistent with an estimateEschrig et al. (2001) for the relative area in which the resonance is suppressed in YBa2Cu3O6.6. The idea of a halo region extending beyond the vortex core was suggested by the scanning tunneling microscopy study of Bi2Sr2CaCu2O8+δ by Hoffman et al.Hoffman et al. (2002) and discussed by Zhang et al.Zhang et al. (2002) A much larger halo region is required to explain the neutron scattering measurementsKatano et al. (2000); Lake et al. (2002); Khaykovich et al. (2002, 2003) of field-induced spin-density-wave order in underdoped La2-xSrxCuO4 and La2CuO4+δ.

We agree with Lake et al.Lake et al. (2001) that the magnetic field induces a response that is closer to magnetic ordering; however, our interpretation of that induced response differs somewhat from their’s. They interpreted the induced response to be a mode within the spin gap, with a peak energy much lower than the peak energy found in the normal state above $`T_c`$. Our results show that changes occur at higher energies as well, so that the induced response is not restricted to the spin-gap region.

It is interesting to compare with a recent inelastic-neutron-scattering studyKimura et al. (2003) of Zn-doped La2-xSrxCuO4. In the muon-spin-rotation study of Nachumi et al.,Nachumi et al. (1996) it was deduced that each Zn dopant reduces the superconducting carrier density by a fractional amount corresponding to a relative area equal to that of a magnetic vortex core. One might then expect that the impact on spin excitations might be similar to that from vortices. Indeed, Kimura et al.Kimura et al. (2003) find that Zn-doping introduces a component of spin fluctuations that extends into the spin gap of the undoped, $`x=0.15`$ parent material. The amount of signal within the spin gap grows with doping, and an elastic component becomes detectable at a Zn concentration of 1.7%. At that level of Zn, $`T_c`$ has been reduced from 37 K to 16 K. That is a larger change in $`T_c`$ than we are able to accomplish in our $`x=0.18`$ sample with experimentally-achievable magnetic fields. Of course, our sample is on the metallic side of the insulator-to-metal crossover identified by Boebinger et al.Boebinger et al. (1996) using applied magnetic fields of 61 T, so that it seems unlikely that we would be able to induce static spin stripe order in it simply by suppressing the superconductivity.

To avoid confusion, we should note that there are differences in the way that we and Kimura et al.Kimura et al. (2003) have presented the inelastic results. In presenting energy and temperature dependence, we have shown $`\chi ^{\prime \prime }`$ measured at a particular q point, whereas Kimura has plotted $`\chi ^{\prime \prime }`$ integrated over q. Variations in $`q`$-width of the inelastic peaks can cause the dependences of these quantities on temperature, energy, etc. to be slightly different. Indeed, looking at the measurements at $`\mathrm{}\omega =9`$ meV and $`T=3`$ K in Fig. 4 (c,d), we see a drop in the peak intensity on applying the field; however the peak area changes much less, since the width grows.

Vojta et al.Vojta et al. (2000) have shown that there is at least one theoretical difference between the effects of a Zn dopant and a vortex: substitution of a Zn atom for Cu effectively introduces a free spin. While these free spins can be detected by probes of the uniform spin susceptibility,Xiao et al. (1990) it is not clear that they should play the dominant role in the observed changes in inelastic scattering. It seems likely that the observed changes must come from a significant range about each Zn, and that they involve a slowing of stripe fluctuations in the vicinity of impurities, similar to the impact of vortices.

## V Summary

We have studied the effect of a magnetic field, applied parallel to the $`c`$ axis, on the low-energy magnetic fluctuations in slightly-overdoped La1.82Sr0.18CuO4. We observe that the enhancement of the incommensurate intensity at 9 meV for $`T<T_c`$ is reduced when the field is applied. Based on this result, we identify the 9-meV peak as a resonance feature in analogy with the commensurate resonance found in other cuprates. Field-induced signal is seen within the spin gap, consistent with an earlier study, and indicating that the applied field, which suppresses the superconductivity within vortex cores, also pushes the magnetic correlations closer to a stripe-ordered state. The intensity of the in-gap signal indicates that it must come from a region substantially larger than that of a vortex core.

## Acknowledgements

JMT is supported at Brookhaven by the U.S. Department of Energy’s Office of Science under Contract No. DE-AC02-98CH10886. CHL’s work at AIST is supported by a Grant from the Ministry of Economy, Trade and Industry of Japan. KY receives support from the Japanese Ministry of Education, Culture, Sports and Science and Technology; Grant-in-Aid for Scientific Research on Priority Areas, Scientific Research (B), Encouragement of Young Scientists, and Creative Scientific Research. This study was supported in part by the U.S.-Japan Cooperative Research Program on Neutron Scattering.