## 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(\sqrt n)$ approximation algorithm that runs in *O*(*n*log*n*loglog*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.

keywords: Computational Geometry, Graphs Theory

### Journal Article (peer-reviewed)

Damian Merrick, Jun Luo, Maarten Löffler, Magdalene G. Borgelt, Marc van Kreveld, Mostafa Vahedi, Rodrigo I. Silveira

Planar Bichromatic Minimum Spanning Trees

Journal of Discrete Algorithms

7, 4, 469–478, 2009

### Workshop or Poster (weakly reviewed)

Damian Merrick, Jun Luo, Maarten Löffler, Magdalene G. Borgelt, Marc van Kreveld, Mostafa Vahedi, Rodrigo I. Silveira

Planar Bichromatic Minimum Spanning Trees

Proc. 23rd European Workshop on Computational Geometry

162–165, 2007

### Technical Report (not reviewed)

Damian Merrick, Jun Luo, Maarten Löffler, Magdalene G. Borgelt, Marc van Kreveld, Mostafa Vahedi, Rodrigo I. Silveira

Planar Bichromatic Minimum Spanning Trees

UU-CS-2007-044, 2007

back to list