Tight bounds for connecting sites across barriers

ABSTRACT

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight-line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines then there is a spanning tree where every barrier is crossed by O(√m) tree edges (connectors), and this bound is asymptotically optimal (spanning tree with low stabbing number). Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Constructions with 3 crossings per barrier and 2n total cost provide a lower bound.We obtain tight bounds on the minimum cost spanning tree in the most exciting special case where the barriers are interior disjoint line segments that form a convex subdivision and there is a point in every cell. In particular, we show that there is a spanning tree such that every barrier is crossed by at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are tight.

REFERENCES

• 1: T. Asano, M. de Berg, O. Cheong, L. J. Guibas, J. Snoeyink, and H. Tamaki. Spanning trees crossing few barriers. Discrete Comput. Geom., 30(4):591--606, 2003.
• 2: B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
• 3: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 4: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 5: M. Hoffmann and C. D. Tóth. Connecting points in the presence of obstacles in the plane. In Proc. 14th Canad. Conf. on Comput. Geom., pp. 63--67, 2002.
• 6: D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12(1):28--35, 1983.
• 7: D. Krumme, G. Perkins, E. Rafalin, and D. L. Souvaine. Upper and lower bounds for connecting sites across barriers. TUFTS-CS technical report 2003-6, Tufts University, Medford, MA, 2003.
• 8: J. Matoušek. Spanning trees with low crossing number. RAIRO Inform. Théor. Appl., 25(2):103--123, 1991.
• 9: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 10: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 11: J. Snoeyink. Open problems session, 1997. 9th Canadian Conference on Computational Geometry.
• 12: Jack Snoeyink , Marc J. van Kreveld, Linear-Time Reconstruction of Delaunay Triangulations with Applications, Proceedings of the 5th Annual European Symposium on Algorithms, p.459-471, September 15-17, 1997
• 13: E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]
• 14: 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
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
crossing number, spanning trees