  We study colored coverage and clustering problems. Here, we are given a
colored point set, where the points are covered by (unknown) $k$ clusters,
which are monochromatic (i.e., all the points covered by the same cluster, have
the same color). The access the colors of the points (or even the points
themselves) is provided indirectly via various queries (such as nearest
neighbor, or separation queries). We show that one can correctly deduce the
color of all the points (i.e., compute a monochromatic clustering of the
points) using a polylogarithmic number of queries, if the number of clusters is
a constant.
  We investigate several variants of this problem, including Undecided Linear
Programming, covering of points by $k$ monochromatic balls, covering by $k$
triangles/simplices, and terrain simplification. For the later problem, we
present the first near linear time approximation algorithm. While our
approximation is slightly worse than previous work, this is the first algorithm
to have subquadratic complexity if the terrain has "small" complexity.
