On Some Geometric Problems of Color-Spanning Sets

摘要

In this paper we study several geometric problems of color-spanning sets: given N points with M colors in the plane, choosing M points with distinct colors such that some geometric properties of those M points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, and the minimum planar spanning tree. We give an O(N log N) expected time algorithm for the maximum diameter problem. For the largest closest pair and the minimum planar spanning tree problems, we give hardness proofs.