Spanning Trees Crossing Few Barriers

We consider the problem of finding low-cost spanning trees for sets of $n$ points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of $m$ barriers. We obtain the following results: (i) if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost $O(\min(m^2,m\sqrt{n}))$; (ii) if the barriers are disjoint line segments, then there is always a spanning tree of cost $O(m)$; (iii) ] if the barriers are disjoint convex objects, then there is always a spanning tree of cost $O(n+m)$. All our bounds are worst-case optimal, up to multiplicative constants.