**Next:** Problem 21: Shortest Paths among Obstacles in 2D

**Previous:** Problem 19: Vertical Decompositions in \R^d

- Statement
What is the complexity of computing a spanning tree of a planar point set P having minimum stabbing number? The

*stabbing number*of a tree T is the maximum number of edges of T intersected by a line.- Origin
Uncertain, pending investigation.

- Status/Conjectures
Solved, October 2003: the problem is NP-complete. Significant advance on approximability in 2009.

- Partial and Related Results
Fekete, Lübbecke, and Meijer [FLM04] proved strong NP-completeness of minimizing the stabbing number or axis-parallel stabbing number or crossing number or axis-parallel crossing number in a perfect matching or spanning tree. They also establish inapproximability by less than a 6/5 factor of minimizing the axis-parallel stabbing number in a perfect matching. They also prove strong NP-completeness of minimizing the axis-parallel crossing number in a triangulation.

The complexity of minimizing the stabbing number or crossing number in a triangulation remains open. Furthermore, it remains open whether any of these problems have constant-factor approximations. See [FLM04] for some ideas.

In the worst case, any set of n points in the plane has a spanning tree of stabbing number O(\sqrt n) [Aga92], [Cha88], [Wel93] and this bound is tight. An O(\sqrt n)-approximation follows from this result.

There has been an advance on approximations [HP09]: Har-Peled designed an algorithm that computes a spanning tree of n points P in \R^d whose crossing number is O(\min( t \log n, n^{1-1/d})), where t the minimum crossing number of any spanning tree of P.

- Appearances
- Categories
stabbing

- Entry Revision History
J. O’Rourke, 2 Aug. 2001; E. Demaine, 16 Jan. 2004; J. O’Rourke, 26 Aug 2009.

- [Aga92]
Pankaj K. Agarwal. Ray shooting and other applications of spanning trees with low stabbing number.

*SIAM J. Comput.*, 21:540–570, 1992.- [Cha88]
Bernard Chazelle. Tight bounds on the stabbing number of spanning trees in Euclidean space. Report CS-TR-155-88, Dept. Comput. Sci., Princeton Univ., Princeton, NJ, 1988.

- [FLM04]
Sándor P. Fekete, Marco E. Lübbecke, and Henk Meijer. Minimizing the stabbing number of matchings, trees, and triangulations. In

*Proc. 15th Ann. ACM-SIAM Sympos. Discrete Algorithms*, pages 430–439, January 2004.- [HP09]
Sariel Har-Peled. Approximating spanning trees with low crossing numbers. http://valis.cs.uiuc.edu/~sariel/papers/09/crossing/, June 2009.

- [MO01]
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42.

*Internat. J. Comput. Geom. Appl.*, 11(5):573–582, 2001. Also in*SIGACT News*32(3):63-72 (2001), Issue 120.- [Wel93]
Emo Welzl. Geometric graphs with small stabbing numbers: Combinatorics and applications. In

*Proc. 9th Internat. Conf. Fund. Comput. Theory*, Lecture Notes Comput. Sci., page ?? Springer-Verlag, 1993.