On the Red/Blue Spanning Tree Problem

Abstract: A geometric spanning tree of a point set S is a tree whose vertex set is S and whose edge set is a set of non-crossing straight line segments with endpoints in S. Given a set of red points and a set of blue points in the plane, the red/blue spanning tree problem is to find a geometric spanning tree for red points and a geometric spanning tree for blue points such that the number of crossing points of the two trees is minimum.

Results:

• If the points are in general position, the red/blue spanning tree problem can be solved in O(n log n) time where n=|S|. The time is optimal.
• If collinear points are allowed, we prove that the problem of deciding whether there exists a geometric spanning path of all the red points and a geometric spanning path of all the blue points without crossing is NP-complete.

Two trees with crossing number 1 (minimum).

paper

@article{bjyz-rbstp-11
, author = {Sergey Bereg and Minghui Jiang and Boting Yang and Binhai Zhu}
, title = {On the Red/Blue Spanning Tree Problem}
, journal = {Theoret. Comput. Sci.}
, year = {2011}
, volume = {412}
, number = {23}
, pages = {2459--2467}
, url = {http://dx.doi.org/10.1016/j.tcs.2010.10.038}
}