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 to the colors of the points (or even the poi...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-05
Main Authors: Ashur, Stav, Har-Peled, Sariel
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Clustering
Color
Complexity
Linear programming
Mathematical analysis
Queries
Terrain
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422