Technical Reports

Given a set M of m distinct points (sites) and a set N of n segments (barriers) in the plane, we address the problem of constructing a planar spanning tree of M of straight edges with minimal cost, where the cost function is the number of times that edges cross barriers (the 'crossing number'). For the restricted problem where barriers form a convex planar subdivision and each face contains exactly one site, we prove a tight bound of 5n/3 total cuts. As for the number of cuts per barrier, we prove that at most 3 cuts per barrier are needed, provide a lower bound of 2 cuts per barrier and develop a linear time algorithm. Asano et al. 99 proved upper bounds of 4 cuts per barrier and a total cost of 4n for the general case, with corresponding lower bounds of 2 and 2n-2. New constructions developed here may apply both to other problems and to tightening the bounds in the general case.