Minimizing the stabbing number of matchings, trees, and triangulations

ABSTRACT

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.

REFERENCES

• 1: Pankaj K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, SIAM Journal on Computing, v.21 n.3, p.540-570, June 1992 [doi>10.1137/0221035]
• 2: Pankaj K. Agarwal , Boris Aronov , Subhash Suri, Stabbing triangulations by lines in 3D, Proceedings of the eleventh annual symposium on Computational geometry, p.267-276, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220308]
• 3: Esther M. Arkin , Michael A. Bender , Erik D. Demaine , Sándor P. Fekete , Joseph S. B. Mitchell , Saurabh Sethia, Optimal covering tours with turn costs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.138-147, January 07-09, 2001, Washington, D.C., United States
• 4: William J. Cook , William H. Cunningham , William R. Pulleyblank , Alexander Schrijver, Combinatorial optimization, John Wiley & Sons, Inc., New York, NY, 1998
• 5: Mark de Berg , Marc van Kreveld, Rectilinear decompositions with low stabbing number, Information Processing Letters, v.52 n.4, p.215-221, Nov. 25, 1994 [doi>10.1016/0020-0190(94)90129-5]
• 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 optimal area. Discrete and Computational Geometry, 23:73--110, 2000.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: M. Held, J. T. Klosowski, and J. S. B. Mitchell. Evaluation of collision detection methods for virtual reality fly-throughs. In Proceedings of the 7th Canadian Conference on Computational Geometry, pages 205--210, 1995.
• 11: John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Journal of Algorithms, v.18 n.3, p.403-431, May 1995
• 12: K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39--60, 2001.
• 13: K. Jain. Personal communication, 2003.
• 14: A. Jüttner. On budgeted optimization problems. Mathematics of Operations Research, to appear.
• 15: T. Kirá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. Matoušek. Spanning trees with low crossing number. Inform. Theor. Appl., 25:102--123, 1991.
• 18: M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 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 b-matchings. 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: Emo Welzl, On Spanning Trees with Low Crossing Numbers, Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, p.233-249, January 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Keywords:
complexity, crossing number, iterated rounding, linear programming relaxation, matching, spanning tree, stabbing number, triangulation