## 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(n3) 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.

keywords: Computational Geometry, Graphs Theory

### Journal Article (peer-reviewed)

, , , , , ,
Planar Bichromatic Minimum Spanning Trees
Journal of Discrete Algorithms
7, 4, 469–478, 2009
http://dx.doi.org/10.1016/j.jda.2008.08.001

### Workshop or Poster (weakly reviewed)

, , , , , ,
Planar Bichromatic Minimum Spanning Trees
Proc. 23rd European Workshop on Computational Geometry
162–165, 2007

### Technical Report (not reviewed)

, , , , , ,
Planar Bichromatic Minimum Spanning Trees
UU-CS-2007-044, 2007
http://www.cs.uu.nl/research/techreps/UU-CS-2007-044.html

back to list