Spanning trees crossing few barriers

Abstract

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), mrootn)) (ii) if the barriers are disjoint line segments, then there is always a spanning tree of cost 0(m); (iii) if the barriers are disjoint convex objects, then there is always a spanning tree of cost 0 (n + m). All our bounds are worst-c se optimal, up to multiplicative constants.