Planar Bichromatic Minimum Spanning Trees

Kimberly Crosbie

Given a set $S$ of red and blue points in the plane, a planar bichromatic minimum spanning tree is a spanning tree of $S$ with minimum total length such that every edge has one red endpoint and one blue endpoint and no two edges cross. It has been shown that computing the planar bichromatic minimum spanning tree in the general case is NP-hard. Currently, the best approximation algorithm is an $O(\sqrt{n})$-approximation algorithm that was presented by Borgelt et al. This talk gives an overview of the problem, outlines an algorithm for a special case and presents the main ideas in Borgelt et al.'s approximation algorithm.