Minimizing the Stabbing Number of Matchings, Trees, andTriangulations
Sándor P. Fekete

Marco E. Lübbecke†

Henk Meijer‡

Abstract

1 Introduction

The (axis-parallel) stabbing number of a given set of line
segments is the maximum number of segments that can beintersected by any one (axis-parallel) line. We investigate
problems of finding perfect matchings, spanning trees, ortriangulations of minimum stabbing number for a given
set of points. The complexity of these problems has beena long-standing open problem; in fact, it is one of theoriginal 30 outstanding open problems in computational
geometry on the list by Demaine, Mitchell, and O’Rourke.

Objective Functions. Typical problems in combinatorial optimization, algorithmic graph theory, or computational geometry deal with minimizing the length of adesired structure: Given a set of points, find a set of line
segments of small total length, such that a certain structural condition is maintained. Among the most popularsuch structures are spanning trees, perfect matchings, or(in a planar geometric setting) triangulations. However,some geometric scenarios motivate other objective functions; one such alternative for measuring the quality of astructure is the total turn cost between adjacent line segments; e.g., see [3].

We show that minimum stabbing problems are NPcomplete. We also show that an iterated rounding technique is applicable for matchings and spanning trees ofminimum stabbing number by showing that there is apolynomially solvable LP-relaxation that has fractional
solutions with at least one heavy edge. This suggests
constant-factor approximations. Our approach uses polyhedral methods that are related to another open problem (from a combinatorial optimization list), in combination with geometric properties. We also demonstrate thatthe resulting techniques are practical for actually solving
problems with up to several hundred points optimally or
near-optimally.
Classification: F.2.2 Nonnumerical Algorithms andProblems
Keywords: Stabbing number, crossing number, matching, spanning tree, triangulation, complexity, linear
programming relaxation, iterated rounding.

Department of Mathematical Optimization, Braunschweig University of Technology, Pockelsstraße 14, D-38106 Braunschweig, Germany.
Email: s.fekete@tu-bs.de .
† Institut für Mathematik, Sekr. MA 6-1, Technische Universität
Berlin, Straße des 17. Juni 136, D-10623 Berlin, Germany. Email:m.luebbecke@math.tu-berlin.de . Visits to Kingston and Stony
Brook in May 2002 were supported by a DFG travel grant.
‡ Dept. of Computing and Information Science, Queen’s University,
Kingston, Ontario, K7L 3N6, Canada. Email: henk@cs.queensu.ca .
Partially supported by NSERC while visiting Braunschweig during fall
2002.

When dealing with structural or algorithmic properties, one can be more interested in yet another objectivefunction called the stabbing number. In order to unify
definitions for different structures and to allow for a consistent notation throughout this paper, we describe this as
a property of a set of line segments: For a given set of line
segments, the stabbing number is the maximum numberof segments that are encountered (in their interior or at an
endpoint) by any infinite line; if we consider only axisparallel lines, we get the axis-parallel stabbing number.
When focusing on the number of objects defined by theline segments, we may consider the closely related crossing number, which arises from considering the number ofconnected components in the intersection with the set ofline segments that we have to cross along a line. In theabsence of connected components of collinear segments(which is the case for matchings), the crossing number isequal to 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.
Related Work. Stabbing problems have been considered for a number of years. The complexity of manyalgorithms in computational geometry is directly dependent on the complexity of ray-shooting, which depends
directly on the stabbing number. Agarwal [1] describes
several applications of spanning trees with low stabbing
number, among them ray-shooting and implicit point lo-

Copyright © 2004 by the Association for Computing Machinery, Inc.
and the Society for industrial and Applied Mathematics. All Rights
reserved. Printed in The United States of America. No part of this bookmay be reproduced, stored, or transmitted in any manner without thewritten permission of the publisher. For information, write to the
Association for Computing Machinery, 1515 Broadway, New York, NY
10036 and the Society for Industrial and Applied Mathematics, 3600
University City Science Center, Philadelphia, PA 19104-2688

437

cations queries (which by themselves have applicationsin polygon containment, implicit hidden surface removal,
polygon placement, etc.). The theoretically best performing data structure for ray tracing in two dimensions isbased on a triangulation of the scene; see Hershberger
and Suri [11]. Agarwal, Aronov, and Suri [2] investigate
the stabbing number of triangulations in three dimensions,where the stabbed objects are simplices. Held, Klosowski,
and Mitchell [10] investigate collision detection in a virtual reality environment; again, we have a dependency on
the stabbing number.
Extremal properties of crossing numbers were considered by Welzl [25] and by Matoušek[17], who showedthat any planar set of n points has a spanning tree with acrossing number of O n  ,  andthere are examples requir
ing a crossing number of Ω n  . Another variant is studied by de Berg and van Kreveld [5]: The stabbing numberof a decomposition of a rectilinear polygon P into rectangles is the maximum number of rectangles intersectedby any axis-parallel segment that lies completely insideof P; they prove that any simple rectilinear polygon withn vertices
admits a decomposition with stabbing numberO log n  , and they give an example of a simple rectilinear polygon
for which any decomposition has stabbing
number Ω log n  . They generalize their results to rectilinear polygons with rectilinear holes. Shewchuk [23]showsthat in d dimensions, a line can stab the interiors ofΘ n  d  2  Delaunay d-simplices. This implies, in particular, that a Delaunay triangulation in the plane may havelinear stabbing number.

good lower bounds, and is closely related to an open problem from another prominent list, this time from the combinatorial optimization community [14, 15]. As a consequence, we are able to deduce an extension of the iterated rounding technique developed by Jain for generalized
Steiner network problems [12]; making additional use of
the geometric structure of the problem, we get the basis
for constant-factor approximations. Finally, we demonstrate by a computational study on various benchmark setsthat our LP-based approach is also practically useful, bothfor solving problems approximately or optimally, by considering integer programming (IP).

Despite of this interest by a fair number of noteworthy researchers, there have been no results or conjectures
whatsoever on the complexity of stabbing problems. In
fact, resolving the complexity of stabbing problems has
been one of the original 30 outstanding open problemsof computational geometry on the list that was first presented by Mitchell and O’Rourke in [19], based on many
years of preceding discussions and informal surveys. An
up-to-date and expanded list is maintained by Demaine,
Mitchell, and O’Rourke and can be found on the internet [6]. In addition to the open complexity status, thereader should take note that stabbing problems have defied all attempts for obtaining good combinatorial lower
bounds, and nothingis known about approximation, other than the factor O n  that can be deduced from Welzl’swork.
Our Work. In this paper, we present the first generalalgorithmic study of stabbing problems. We resolve theopen problem of complexity for various structures; ourtechnique is quite general, and it seems clear that it canbe extended to other versions. We also describe a generaltechnique based on Linear Programming (LP) that yields

438

Our results in detail:We prove that deciding whether a point set has aperfect matching of axis-parallel stabbing number
5 is an NP-complete problem; we also extend thisresult to general stabbing number.
We give an NP-completeness proof for finding aspanning tree of axis-parallel or general stabbing
number, and hint at a hardness proof for axis-parallelor general crossing number.
We prove that finding a triangulation of minimumaxis-parallel crossing number is NP-hard.
We describe an LP-based class of lower bounds thatcan be evaluated in polynomial time. From a theoretical point of view, we use the ellipsoid method;the existence of a strongly polynomial algorithm fora closely related class of problems is subject to an
open problem from the list [14, 15].
We give results on the structure of fractional verticesof the resulting LP-relaxation: For matching, weshow that there always is an edge with weight atleast 1/5, while for spanning trees, there always is
an edge with weight greater than 1/3. This allows
applying an iterated rounding technique, similar tothe one developed by Jain for generalized Steiner
network problems; this should imply constant-factor
approximations.
We describe the results of a computational study.
Using a diverse set of benchmark instances (basedon TSPLIB, Solomon’s vehicle routing problems,
and two different types of random instances) we areable to compute optimal and near-optimal solutions
for instances up to several hundred points. This
demonstrates 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). Results indicate far betterapproximation quality than the theorically possible
factors of 5 or 3, respectively.
It should be noted that our positive (LP-based) results
do not make any assumptions on the structure of the point
set: They can be used for point sets in degenerate as wellas in general position, and can be applied to any familyof stabbing lines that can be evaluated by consideringa subset of polynomially many representatives. On theother hand, the point sets constructed in our hardness
proofs make use of collinear points.
The rest of this paper is organized as follows. After some basic definitions and notation in Section 2, wegive sketches of our various hardness proofs in Section 3,
with details omitted from this extended abstract. 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; the resulting algorithms appear to be constant-factor approximations. Section 6 presents a detailed computational study
on perfect matchings of low stabbing number. Final concluding thoughts and miscellaneous results and problems
are presented in Section 7.
2

Preliminaries

In the following, we consider a planar point set P of
cardinality n. When dealing with matchings, we assume
that n is even, if necessary by omitting one of the points.

that stabbing and crossing number or depth are the samefor matchings.
3 Complexity
In this section we give proofs and proof sketches that
virtually all variants of minimum stabbing problems are
NP-hard. Our technique is rather general and should beapplicable to other variants as well. In this extended
abstract, we give only proof sketches; full details can befound in the full version of the paper.
3.1 Matchings
T HEOREM 3.1. Deciding whether St-Mat2 P 
strongly NP-complete problem.

5 is aProof. We prove the theorem by using a reduction from
3SAT [9]. Assume we have a Boolean expression denotedby B x 0  x1  xn  1  with n variables and k clauses ofthree literals. We construct a set of points P that has
a matching M of stabbing number 5 if and only if theBoolean expression can be satisfied. For the overalllayout see Figure 1. Note the collinear sets of points thatfunction as “barriers”: As they already require a stabbing
number of 5, they must not be crossed by additional line
segments, thus imposing a clear combinatorial structurethat is exploited in the proof.

Each variable gadget allows two feasible matchings;
the particular choice represents a truth assignment for aGiven a set of line segments L, the stabbing number
particular variable, which in turn imposes requirementsof a line is the number of segments of L that are interon how the literal gadgets in the respective columns may
sected by . The stabbing number of L is the maximum
be chosen. Clauses are represented by three literal gadgets
stabbing number over all lines ; the axis-parallel stabin the same row; the overall construction implies that thebing number of L is the maximum stabbing number overstabbing number of the row of a clause is at most five,all axis-parallel lines . In the rest of this paper, the set
iff at least one literal gadget in this row contributes only
L will arise as a matching, spanning tree, or triangulaone stabbed line segment, meaning that at least one literaltion of a planar point set P, and our objective is to findsatisfies the clause.
such a structureof minimum stabbing number. We denoteby St-Matall P  the minimum stabbing
number among all C OROLLARY 3.1. There is no α-approximation algomatchings of P, and by St-Mat2 P  the minimum axis- rithm for St-Mat  P  with α  6  5.
2
parallel stabbing numberof all matching of P. Similarly,
we denote by St-Treall P  the minimum stabbing
num- C OROLLARY 3.2. Computing St-Matall P  is a weakly
ber of all spanning trees of P, by St-Tre2 P  the mini- NP-hard problem.
mum axis-parallel
stabbing number of all spanning treesof P; by St-∆ all P  the minimum  stabbing number of all Proof. We apply a perturbation technique, similar to thetriangulations of P, and by St-∆ 2 P  the minimum axis- one in [8]. Use the same construction as for the hardness
parallel stabbing number of all triangulations of P.
proof for the axis-parallel case. Consider the grid formed
If we are not interested in the number of line seg- by the coordinates of the resulting point set. This grid
distances between thements in L encountered by a line , but in the number is modified such that the interpoint2nof connected components of L , we get the crossing points of the same gadget are Θ ε  . Furthermore, thenumber. For matchings, trees, and triangulations,we  use rest of the grid is perturbed by powers of ε, such that only
the analogous
abbreviations
Cr-MatP,Cr-Mat2 P  , axis-parallel lines can stab more than two gadgets. Now it


 all

Cr-Tre all P  , Cr-Tre 2 P  , Cr-∆ all P  , Cr-∆ 2 P  . Note is easy to see that only axis-parallel lines are critical. 439

open (satisfying) channel

top rows

closed (non-satisfying) channel
non-satisfying literalvertical barriers

satisfying literalhorizontal barriers
x0 x0

reducers

x1 x1

x2 x2

x3 x3

x3
x2
x1
x0

clause 0
clause 1
clause 2

Figure 1: Overall layout for St-Mat2 P  .

3.2 Spanning Trees. The basic construction for showing hardness of finding a spanning tree of minimum stabbing number is very similar to the one for matchings. As
before, we use barriers to restrict possible connections:
We make use of the arrangement shown (in horizontal orientation) in Figure 2.

L EMMA 3.4. Let S be the arrangement of points shownin Figure 3, with barrier gadgets placed and sized asindicated, and let P  S. Then any spanning tree of P
that has stabbing number at most k  1 uses either thetwo “true” or the two “false” edges.

The overall layout of the construction is shown in
Figure4. For proving hardness of finding a spanning tree
L EMMA 3.3. Let S be the arrangement of 3k pointsofminimumcrossing number we use the following barrier
shown in Figure 2, and let P  S have no other points
gadget.
Foraproof note that each elementary 2  2 cyclein the horizontal strip indicated by shading. If P has aspanning tree T with stabbing number c  1, then no edge of the gadget must have at least one edge not present ina tree; then the claim follows by pigeonhole principle.
of T crosses the shaded region.
Finally, the NP-hardness proof for all directions follows
again by making only the axis-parallel directions to beckcritical.
c
c

(a)

(b)

c

Figure 2: A barrier gadget: (a) In a spanning tree of
stabbing number c  1, no line segment may cross theshaded region. (b) Symbol for the barrier gadget; thedotted line indicates the blocked strip.
The variable gadgets look as in Figure 3. Note theuse of barrier gadgets, and the remaining numbers ofsegments that may cross the induced dotted lines.

2(c−1) +2

Figure 5: A barrier gadget for showing hardness ofminimizing the crossing number of a spanning tree.

440false
true
k−2
k−2
k−2

k−2

k−2

k−2
k−5−2(n−i)

k−2kk−5−2(n−i)

k−2

k

k

k

(b)

(a)

Figure 3: A gadget for variable xi : (a) In a spanning tree of stabbing number k  1, either the “true” or the “false”
setting is chosen. (b) Symbol for the variable gadget.

x3
symbol for literals
k−2n+1
false literalx2

true literal
k−2n−1x1k−2n−3c1x3

k−2n−2

x1

x2

k

c2

x3

x1

k−2n−2x2kc3 k−2n−2

x2

x1

x3

Figure 4: The overall layout for the hardness proof for spanning trees. n is the total number of variables, k a sufficiently
large number; in questionis the existenceof a spanning
tree with stabbing number k  1. Shown is the representation
of the 3SAT instance x1  x2  x̄3  x̄1  x2  x3  x1  x̄2  x3  , for n  3.

441



L EMMA 3.5. Let S be the k  c  1  2  c arrangement matching given by x.
of points shown in Figure 5, and let P  S. If P has a(4.1)∑ xi j  1 , i ! V
spanning tree T with crossing number c, then no otheri j ) δ * i+edge of T crosses the shaded region.
(4.2)∑ xi j - 1 , S % V  ( S ( oddi j ) δ * S+

Summarizing, we state:

x- 0

(4.3)

In a seminal paper Edmonds [7] showed that this polyhedral description is also sufficient in the sense that theextreme points of the polytope Π defined by (4.1)–(4.3)
are exactly the incidence vectors of perfect matchings in
3.3 Triangulations. We use the following terminology. G. Despite the fact that there are exponentially many soA horizontal line is a set of points that are on a horizontal called blossom inequalities (4.2) one can solve a linear
line. A vertical line is a set of points that are on a vertical program over Π in strongly polynomial time [4].
line. A row consists of two horizontal lines, and the
Now we wish to minimize the stabbing number k and(empty) space between them. A column consists of two add to Π
vertical lines, and the (empty) space between them.
(4.4)


T HEOREM
3.2. It is  NP-hard to determine
St-Tre2 P  ,
St-Treall P  , Cr-Tre 2 P  , or Cr-Tre all P  .

∑ 3 xi jk,stabbing line

i j:i j .0/* d +21 0/d  in direction d 

L EMMA 3.6. Consider a row consisting of two horizontal lines in P, having a and b points, respectively. The In principle, there are infinitely many constraints of thishorizontal stabber of this row encounters at least a  b  2 type, even for one direction. Note, however, that when
triangles in any triangulation of P.
sweeping a stabbing line in direction d the stabbing number changes only at a vertex. Therefore, we only need tocheck a linear number of lines in each direction.
For the
A detailed proof can be found in the full paper. The
same reason, “all” directions reduce to the O n2  combilemma analogously holds for two vertical lines that form
natorial directions determined by all pairs of vertices of G.
a column. When a row consists of two horizontal lines
When requiring integrality of x and minimizing k in the rethat have Cr-∆ 2 P  2 points altogether, we call it fullsulting integer program yields exactly St-Mat P  . Whenor fully triangulated. In a triangulation that achieves theintegrality is relaxed to (4.3), this linear  programming relower bound of the lemma this row has the property that
laxation gives a lower bound on St-Mat P  . The solution
all edges along the horizontal lines have to be present. The
x will in general be fractional, and we speak of fractionalsame applies to full columns, and this is the way how westabbing number in this context.
will use the lemma.
The resulting LP can be solved in weakly polynomial
time by means of the ellipsoid method [18]: Separating vi
T HEOREM 3.3. Finding Cr-∆ 2 P  is NP-hard.
olated blossom inequalities is possible in polynomial time[20], and there are only polynomially many stabbing constraints. It should be noted that this is closely related to
The proof is based on another reduction of 3SAT. The
another well-considered open problem: [14, 15] asks formechanics of gadgets is similar to our previous two rea strongly polynomial algorithm for finding an optimal
ductions. Details can be found in the full version of thematching in the presence of a single general “budget” conpaper. See Figure 6 for a schematic layout of a represtraint, which is a general version of stabbing constraints.
senting
point set P for the 3SAT instance B x 0  x1  x2  This illustrates that giving a strongly polynomial algox 0  x1  x̄2  x 0  x̄1  x2  x̄ 0  x̄1  x̄2  .
rithm for our class of LPs may not be an easy task, eventhough it is the intersection of two well-behaved polyhe4 Linear Programs for Stabbing
dra. This difficulty has been known for other classes of
4.1 Linear Programs and St-Mat P  . Thinking of P intersecting polyhedra [22].
as the vertex
set V of a straight-line embedded completegraph G  V  E  , a handsome representation of a perfectmatching M is by its edge incidence vector x !#" 0  1 $ E ,where xi j   1 if i j ! M and xi j  0 otherwise. For S % V
denote by δ S &'" i j ! E ( i ! S  j ! S $ . The following
linear inequalities are necessarily satisfied for a perfect

4.2 Linear Programs and St-Tre P  . There are several polynomial-size formulations for spanning trees [16].
However, even though exponential in size, the following
cut-based LP formulation turns out to have some particularly useful properties:

442









Figure 6: Overall layout for Cr-∆ 2 P  . Clauses are x 0  x1  x̄2  , x 0  x̄1  x2  , and x̄ 0  x̄1  x̄2  , with x 0  false
and x1  x2  true. Arrows indicate full rows and columns, light or dark shading indicates true or false variables andliterals.

(4.5)∑ xi j of vertices, there is a guaranteed lower bound on thesize of a cut. Integer programs of this type have beencalled generalized Steiner network problems. It is known
that these problems do not tend to have nicely structured
fractional vertices. This does not get better in the presenceof stabbing constraints. In the full paper we provide
examples with edges of rather small fractional weight.
This prohibits a straightforward approximation by simply
rounding up a fractional solution.

n 1i j) E(4.6)∑ xi j -i j ) δ * S+

(4.7)

1 , S % V∑ xi j 4( S (5 1 , S % V i j ) E * S+

(4.8)

x-

0

with the additional stabbing constraints(4.9)
∑ xi j k , stabbing line d  in direction d i j:i j .0/6* d +23 1 0/

Again, solving this LP when minimizing k can beachieved in (weakly) polynomial time.
5

Iterated Rounding

Key ingredients of the linear programs described in theprevious section are constraints having a cut structure: We
require that for any set from a given family of subsets

A very elegant general technique that overcomes
these difficulties and achieves a 2-approximation algorithm for generalized Steiner networks problems was presented by Jain in [12]: Based on a polyhedral argument,
he established that any fractional solution of a generalized
Steiner network LP must have an edge of weight at least
1/2. From this, he derived an approximation algorithm byiteratively rounding up the weight of the heaviest edges,
and re-solving the LP with these fixed edge weights.
It is natural to consider such an approach for our LPs
for deriving approximation methods for stabbing problems, in particular for matchings and spanning trees, as
the stabbing constraints also have cut structure. How-443

ever, Jain’s crucial lemma guaranteeing a heavy edge ina fractional solution does no longer apply in the presenceof stabbing constraints: Figure 7 shows a matching instance for which the optimal fractional axis-parallel stabbing number is achieved by a unique solution with maximum edge weight 1/3.

This sets the stage for an iterated rounding procedure:At each iteration, fix the weight of an edge of maximum
fractional weight to 1, and resolve the linear program. In
each iteration, the number of edges with fractional weightis reduced, so we get an overall polynomial method forfinding an integral solution.

1/3
1/3

1/3

1/3
1/3
1/3

1/3
1/3

1/3

1/3

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 n  1, and the number of edges is at
most 3n  6, implying that the average weight is largerthan 1/3.

1/3
1/3

Figure 7: An optimal fractional solution with maximum
edge weight 1/3.
However, using additional geometric properties, we
can still establish lower bounds. Our proofs are based on
the following lemmas.

It should be noted that even though the key ingredient
for an iterated rounding procedure is provided by Theorem 5.1, there is still one element missing for establishing that these polynomial algorithms are indeed constantfactor approximation algorithms: As the objective function is a maximum, not a sum, we still need an extra argument to assure that Jain’s overall approach does indeed
work. We are hopeful that this argument can be completed[13]. As we show in the following Section 6, the practical
performance seems to be even better than the theoreticallypossible guarantees of 5 and 3.
6 Computational Results

Test suite. We compiled a test suite of various instances on which we evaluated our LP/IP approaches
and the iterated rounding technique for St-Mat2 P  . The
suite includes ten instances with up to 442 points fromthe TSPLIB[21]; the C-class (“clustered”) of Solomon’s
instances of the vehicle routing problem [24] with 100
points each; 25 regular grids with 20 to 360 points, based
L EMMA 5.2. For any set of points in the plane, there is a on grids of size 5  5 up to 20  20 in which 20% ranfractional spanning tree x of minimum stabbing number, domly chosen points are removed; and a set of instancessuch that the support graph of x is planar. Such a with up to 100 random points in the plane. Tables 1 and 2
fractional spanning tree can be found in polynomial time. display our preliminary results on a Pentium III 700MHz
PC with 1GB main memory running Linux. LPs and IPs
Both proofs use an uncrossing 2-exchange argument. are solved by CPLEX8.0, CPU times are listed in seconds.
Note that the proof for Lemma 5.1 requires some extra Table entries bearing the † sign indicate an exceeding ofcare because of the blossom inequalities. A detailed proof our CPU time limit of four hours for solving the IP, i.e.,
can be found in the full paper. The proof of Lemma 5.2 is computing the exact optimum.
almost completely analogous.
Some brief observations. In LP solutions variables
may
assume rather arbitrary fractional and small values;
T HEOREM 5.1. For any even set of points in the plane,
thisisalso true when blossom inequalities are added. The
there is a fractional perfect matching x of minimum stabcolinearityof points in the grid instances enables us to rebing number that has an edge of weight at least 1/5. Forduce
thenumberof stabbing constraints, resulting in sigany set of points in the plane, there is a fractional spannificantly
reducedcomputation times. The clustering ofning tree x of minimum stabbing number that has an edge
pointsinthevehiclerouting instances obviously facilitateof weight more than 1/3.
the LP/IP solution process, as was to be expected. HowProof. For both problems, consider a fractional vertex ever, this observation is interesting in practice where thewith a planar support graph. To see the claim for match- data is usually well structured as opposed to randomly disings, note that there must be a vertex with degree at most tributed.

L EMMA 5.1. For any even set of points 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.

444

Instance
ulysses22
berlin52
lin105bier127
u159
ts225
tsp225a280
lin318pcb442
c101
c102
c103
c104
c105
c106
c107
c108
c201
c202
c203
c204
c205
c206
c207
c208

LP opt1.992308
2.815158
5.500000
4.330856
15.000000
13.750000
11.500000
10.500000
8.113143
16.500000
7.000000
7.000000
7.000000
7.000000
7.000000
7.000000
7.000000
7.000000
6.000000
6.000000
6.000000
6.000000
6.000000
6.000000
6.000000
2.953237

LP CPU
0.01
0.52
1.21
5.64
1.76
5.37
62.06
55.12
131.54270.03
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.10
0.50
0.45
0.46
0.46
0.46
0.46
0.46
0.58

IP opt2
4
infeas.
infeas.
infeas.
infeas.
infeas.
7 12
7 12
7 19
7
7
7
7
7
7
7
7
6
6
6
6
6
6
6

IP CPU
0.05
8.86
†
†
†
†
†
†
†
†
1.75
1.75
1.75
1.75
1.75
1.75
1.75
1.75
2.00
2.00
1.95
1.95
1.95
1.92
1.95
†

The stabbing number obtained from iterated rounding
is often very close to the LP lower bound, and in our
experiments it is never off the optimal value by morethan a factor of 2; typically, it is much better, and mostly
within about 20% of the optimum. We observe that the“bad moves” are made only in the final iterations of theiterated rounding. For instance, about 100 iterations areneeded for lin318 (with 318 points), the LP optimum is
at 8.113, and the LP value exceeds 9.000 only in the lastten iterations, where a value of 11 is reached. We also
experimented with a “one good shot at once” approachthat is based on the fact that each fractional vertex is theconvex combination of perfect matchings, by finding amaximum weight perfect matching in the support graphof the LP solution. This usually gives even better feasible
solutions than for iterated rounding (with one exception
in our test suite of problems). This technique certainly
deserves further evaluation both from a computational andfrom a theoretical point of view, and a discussion will be
included in the full paper.

iter. rounding
2
5
7
5
15
16
12
13
11
18
8
8
8
8
8
8
8
8
7
7
7
7
7
7
7
5


Table 1: Comparison of bounds for St-Mat2 P  and iterated rounding: TSPLIB and clustered instances.

Instance
grid5agrid5bgrid5cgrid5dgrid5egrid8agrid8bgrid8cgrid8dgrid8egrid10agrid10b
grid10c
grid10d
grid10e
grid15agrid15b
grid15c
grid15dgrid15e
grid20agrid20b
grid20c
grid20d
grid20e
rand10a
rand10b
rand10c
rand10d
rand10e
rand50a
rand50b
rand50c
rand50d
rand50e
rand100a

LP opt2.500000
2.750000
2.750000
2.000000
2.500000
5.003205
5.125000
5.000000
5.428571
5.403226
4.250000
4.250000
5.250000
4.500000
5.000000
6.000000
7.500000
6.000000
6.500000
6.750000
9.166667
9.250000
9.500000
9.500000
10.000000
1.750000
1.833333
1.750000
1.700000
1.812500
2.594823
2.628112
2.668918
2.661581
2.789609
3.376247

LP CPU
0.00
0.00
0.01
0.00
0.00
0.04
0.05
0.04
0.04
0.04
0.12
0.10
0.11
0.07
0.03
0.73
0.47
1.00
0.24
0.74
15.38
20.99
8.70
26.69
20.43
0.00
0.00
0.00
0.00
0.00
0.25
0.23
0.23
0.22
0.33
5.57

IP opt
3
3
3
3
3
6
6
5
6
6
5
5
6
5
5
6
8
6
7
7
7 11
7 11
7 11
7 11
7 11
2
2
2
2
2
3
3
4
4
4

IP CPU
0.01
0.02
0.02
0.03
0.02
0.17
0.21
0.12
0.19
0.29
0.68
0.40
245.28
13.58
1.36
8.40
9.90
3.27
†
3.91
†
†
†
†
†
0.01
0.00
0.01
0.01
0.01
19.83
1.91
30.77
15.99
25.54
†

iter. rounding
3
3
4
3
3
6
6
6
7
6
6
6
6
6
6
7
8
6
7
7
12
11
11
11
12
2
2
2
2
2
5
4
4
4
5
6


The stabbing constraints seem to completely destroy
the polyhedral structure of the matching polytope. Halfof the TSP instances are infeasible (because of an odd
number of points), and this is not detected by the CPLEX
IP solver within 4 hours. Iterated rounding terminatesin this case with a non-perfect matching with one point
unmatched.
Even though our prototypes are not yet ready to solve
even larger instances, they may serve as a good starting
point for the development of an industrial strength code.
We plan to include
more computational
results, in particular for St-Matall P  and St-Tre2 P  , in the full paper. We
also plan tests with IP formulations for triangulations.
7 Notes and Conclusion
We have shown that various versions of stabbing problems are NP-hard, and demonstrated how an IP/LP-based
approach may be useful for solving and approximating instances. We expect a number of extensions of this workand hope to include more details and results in a forthcoming full journal version. Here we only mention a numberof other aspects that are also possible.
Clearly the most interesting open problem is a proof
that our iterated rounding technique is indeed a constantfactor approximation algorithm, with a performance guarantee of 5 for matchings, and 3 for spanning trees.

Table 2: Comparison of the LP/IP bounds for St-Mat2 P and iterated rounding: grid and random instances.

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 easytask. From some solvable special cases, we only note one:

445





T HEOREM 7.1. St-Tre2 P  =2 and St-Matall P  =2 canbe decided in polynomial time.
One may also ask for the average instead of the maximum stabbing number, and refer to the average over all
possible lines intersecting a set of line segments, insteadof just a combinatorial set of representatives. This, however, amounts to solving problems of minimum length,with all implications to hardness and approximation.
T HEOREM 7.2. A set of line segments has minimum average (axis-parallel, resp.) stabbing number, iff the overall
Euclidean (Manhattan, resp.) length of all line segments
is minimum.
Finally, the closely related question of investigating
maximum stabbing-independent subsets, i.e., subsets oflines with stabbing number 1, may be interesting in its
own right. Decompositions into stabbing-independent
subsets may also be a combinatorial approach for getting
approximation methods for stabbing problems.
Acknowledgments
We thank Joe Mitchell for pushing us to work on thisproblem, and repeated discussions that assured further
progress. We also thank Kamal Jain for some discussions
on iterated rounding.
References[1] P.K. Agarwal. Ray shooting and other applications ofspanning trees with low stabbing number. SIAM Journal
on Computing, 21(3):540–570, 1992.
[2] P.K. Agarwal, B. Aronov, and S. Suri. Stabbing triangulations by lines in 3D. In Proceedings of the 11th ACM
Symposium on Computational Geometry, pages 267–276,
1995.
[3] E.A. Arkin, M.E. Bender, E.D. Demaine, S.P. Fekete,
J.S.B. Mitchell, and S. Sethia. Optimal covering tours withturn costs. In Proceedings of the 12th Annual ACM-SIAM
Symposium on Discrete Algorithms, pages 138–147, 2001.
[4] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and
A. Schrijver. Combinatorial Optimization. Wiley, New
York, 1998.
[5] M. de Berg and M. van Kreveld. Rectilinear decompositions with low stabbing number. Inform. Process. Lett.,
52(4):215–221, 1994.
[6] E.D. Demaine, J.S.B. Mitchell, and J. O’Rourke. The open
problems project. http://cs.smith.edu/˜orourke/
TOPP/Welcome.html, 2003.
[7] J. Edmonds. Maximum matching and a polyhedron with
0,1-vertices. J. Res. Nat. Bur. Standards, 69B:125–130,
1965.

[8] S. P. Fekete. On simple polygonalizations with optimalarea. Discrete and Computational Geometry, 23:73–110,
2000.
[9] M.R. Garey and D.S. Johnson. Computers and Intractability—A Guide to the Theory of NP-Completeness. W.H.
Freeman and Company, San Francisco, 1979.
[10] M. Held, J.T. Klosowski, and J.S.B. Mitchell. Evaluation of collision detection methods for virtual reality flythroughs. In Proceedings of the 7th Canadian Conference
on Computational Geometry, pages 205–210, 1995.
[11] J. Hershberger and S. Suri. A pedestrian approach to ray
shooting: Shoot a ray, take a walk. J. Algorithms, 18:403–
431, 1995.
[12] K. Jain. A factor 2 approximation algorithm for thegeneralized Steiner network problem. Combinatorica,
21(1):39–60, 2001.
[13] K. Jain. Personal communication, 2003.
[14] A. Jüttner. On budgeted optimization problems. Mathematics of Operations Research, to appear.
[15] T. Király. EGRES list of open problems in combinatorial optimization. http://www.cs.elte.hu/egres/problems/prob_22/index2.html, 2002.
[16] T.L. Magnanti and L.A. Wolsey. Optimal trees. In M.O.
Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser,
editors, Network Models, volume 7 of Handbooks in Operations Research and Management Science, chapter 9,
pages 503–616. North-Holland, 1995.
[17] J. Matoušek. Spanning trees with low crossing number.
Inform. Theor. Appl., 25:102–123, 1991.
[18] M.Grötschel, L. Lovász, and A. Schrijver. Geometric
Algorithms and Combinatorial Optimization. SpringerVerlag, Berlin, 1988.
[19] J.S.B. Mitchell and J. O’Rourke. Computational geometry
column 42. Int. J. Comput. Geom. Appl., 11(5):573–582,
2001.
[20] M. Padberg and M.R. Rao. Odd minimum cut-sets and bmatchings. Mathematics of Operations Research, 7:67–80,
1982.
[21] G. Reinelt. TSPLIB – A traveling salesman problem
library. ORSA J. Comput., 3(4):376–384, 1991.
[22] A. Schrijver. Personal communication, 2002.
[23] J.R. Shewchuk. Stabbing Delaunay tetrahedralizations.
Unpublished Manuscript, 2002. Dept. Electrical Engineering and Computer Science, UC Berkeley, CA.
[24] M.M. Solomon. VRPTW benchmark problems. http://w.cba.neu.edu/˜msolomon/problems.htm, 2003.
[25] E. Welzl. On spanning trees with low crossing numbers.
In B. Monien and Th. Ottmann, editors, Data Structuresand Efficient Algorithms, volume 594 of Lecture Notes in
Computer Science, Berlin, 1992. Springer-Verlag.

446