Problem 20: Minimum Stabbing Spanning Tree

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 $\mathbb {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

[MO01]

Categories

stabbing

Entry Revision History

J. O'Rourke, 2 Aug. 2001; E. Demaine, 16 Jan. 2004; J. O'Rourke, 26 Aug 2009.

Bibliography

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.