Optimal Bichromatic Plane Spanning Trees on Special Point Sets

Kimberly Crosbie

Carleton University

Given a set $R$ of red points and a set $B$ of blue points, we desire to find $T^*$, a minimum weight spanning tree such that every edge has one red endpoint and one blue endpoint and no two edges cross. We call $T^*$ a bichromatic plane minimum spanning tree. We say a point set is semi-collinear when the blue points lie on a line and the red points lie on one side of the line. We present an $O(|B|^3 |R|^2)$ running time algorithm for finding $T^*$ on a set of semi-collinear points. Additionally, we describe changes that can be made to the algorithm presented to solve other related problems. Finally, we describe properties of $T^*$ on semi-collinear point sets.