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 to 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 if the number of clusters is a constant, then 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. 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.
翻译:我们研究彩色覆盖和聚集问题。 在这里, 我们得到一个彩色的点数, 点由( 未知的) $k$ 组群覆盖( 未知的) 的聚点组成, 它们是单色的( 即同一组群中包括的所有点, 都有相同的颜色 ) 。 点的颜色( 甚至是点本身的点) 可以通过不同的查询间接提供 。 我们显示, 如果组群的数量是一个常数, 那么就可以使用多色数来正确推断所有点的颜色( 即, 计算点的单色组合 ) 。 我们调查了这个问题的几种变种, 包括未解的线性编程, 覆盖以美元计单色球的点, 以 $ 的三角形/ 隐性为覆盖, 以及地形简化 。 对于后期的问题, 我们提出第一个接近线性时间缩略算法 。 虽然我们的近似值比先前的工作要差一点, 但这是第一个算法, 如果地形“ 轻微复杂 ”,, 则具有次二次的复杂 。