Planar Bichromatic Minimum Spanning Trees

Given a set S of n red and blue points in the plane, a planar bichromatic minimum spanning tree is the shortest possible spanning tree of S, such that every edge connects a red and a blue point, and no two edges intersect. We show that computing this tree is NP-hard in general. We present an O(n^3) time algorithm for the special case when all points are in convex position. For the general case, we present a factor O(root n) approximation algorithm that runs in O(n log n log log n) time. Finally, we show that if the number of points in one color is bounded by a constant, the optimal tree can be computed in polynomial time.