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)

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
http://dx.doi.org/10.1016/j.jda.2008.08.001

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
http://www.cs.uu.nl/research/techreps/UU-CS-2007-044.html

back to list