The (axis-parallel) stabbing number of a given set of line segments
is the maximum number of segments that can be intersected by
any one (axis-parallel) line. We investigate problems of finding
perfect matchings, spanning trees,
or triangulations
of minimum stabbing number for a given set of points.
The complexity of these problems has been a long-standing open problem;
in fact, it is one of the original 30 outstanding
open problems in computational geometry on the
list
by Demaine, Mitchell, and O'Rourke.
We show that minimum stabbing problems are NP-complete. We
also show that an iterated rounding technique is applicable
for matchings and spanning trees of minimum stabbing number
by showing that there is a polynomially 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 that the resulting techniques are practical for
actually solving problems with up to several hundred points optimally
or near-optimally.
