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³) time algorithm for the special case when all points are in convex position. For the general case, we present a factor $O(\sqrt n)$ approximation algorithm that runs in O(nlognloglogn) 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.

Journal Article (peer-reviewed)

Workshop or Poster (weakly reviewed)

Technical Report (not reviewed)

back to list