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(sqrt{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.

The Honey-comb: an example of the worst case lower bound for the global crossing number (5/3n) and the crossing number per segment (at most 2 crossings)

[1] "Tight Bounds for Connecting Sites Across Barriers", D. Krumme, E. Rafalin, D. Souvaine and C. Toth, submitted for publication ACM SoCG

[2] "Upper and Lower Bounds for Connecting Sites Across Barriers", D. Krumme, G. Perkins, E. Rafalin, D. Souvaine, TUFTS-CS Technical Report, TR-2003-6, Tufts University

[3] "Spanning trees with low crossing number",J. Matousek, RAIRO Inform. Theor. Appl., 25 (2), 1991, pages 103-123

[4] "Spanning trees crossing few barriers",T. Asano, M. de Berg, O. Cheong, L. Guibas,J. Snoeyink, and H. Tamaki, Proc. of the 15th Annual Symp. on Comput. Geom., pages 41-48

[5] "Connecting Points in the Presence of Obstacles in the Plane", Michael Hoffmann and Csaba D. Toth, Proc. of the 14th Canad. Conf. on Comput. Geom., pages 63-67