Connecting colored point sets
O. Aichholzer, F. Aurenhammer, T. Hackl, and C. Huemer
We study the following Ramsey-type problem. Let
two-colored set of
points in the plane. We show how to construct, in
time, a crossing-free spanning tree
a crossing-free spanning tree
, such that both the number of
and the diameters of
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 [#!T!#] that is less efficient in implementation and does
not guarantee a diameter bound.
Reference: O. Aichholzer, F. Aurenhammer, T. Hackl, and C. Huemer.
Connecting colored point sets.
Discrete Applied Mathematics, 155:271-278, 2007.