Connecting colored point sets

We study the following Ramsey-type problem. Let S=B∪RS=B∪R be a two-colored set of n   points in the plane. We show how to construct, in O(nlogn) time, a crossing-free spanning tree T(B)T(B) for B  , and a crossing-free spanning tree T(R)T(R) for R  , such that both the number of crossings between T(B)T(B) and T(R)T(R) and the diameters of T(B)T(B) and T(R)T(R) are kept small. The algorithm is conceptually simple and is implementable without using any non-trivial data structure. This improves over a previous method in Tokunaga [Intersection number of two connected geometric graphs, Inform. Process. Lett. 59 (1996) 331–333] that is less efficient in implementation and does not guarantee a diameter bound. Implicit to our approach is a new proof for the result in the reference above on the minimum number of crossings between T(B)T(B) and T(R)T(R).