Next: Problem 21: Shortest Paths among Obstacles in 2D
Previous: Problem 19: Vertical Decompositions in \R^d
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.
Uncertain, pending investigation.
Solved, October 2003: the problem is NP-complete. Significant advance on approximability in 2009.
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.
stabbing
J. O’Rourke, 2 Aug. 2001; E. Demaine, 16 Jan. 2004; J. O’Rourke, 26 Aug 2009.
Pankaj K. Agarwal. Ray shooting and other applications of spanning trees with low stabbing number. SIAM J. Comput., 21:540–570, 1992.
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.
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.
Sariel Har-Peled. Approximating spanning trees with low crossing numbers. http://valis.cs.uiuc.edu/~sariel/papers/09/crossing/, June 2009.
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.
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.