Connecting colored point sets ?
We study the following Ramsey-type problem. Let S=B?R S = B ? R be a two-colored set of n  points in the plane. We show how to construct, in O ( n log n ) 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) 331333] 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 ) .
spanning trees bicolored point set crossing properties