On Undecided LP, Clustering and Active Learning

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.