Spanning trees crossing few barriers
Tetsuo Asano, Mark de Berg, Otfried Cheong, Leonidas Guibas, Jack Scott Snoeyink, Hisao Tamaki · 1999
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:if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost O(min(m2, mfi)); if the barriers are disjoint line segments, then there is always a spanning tree of cost O(m); if the barriers are disjoint fat objects, discs for example, then there is always a spanning tree of cost O(n + m).All our bounds are worst-case optimal.