On undecided LP, clustering and active learning

Stav Ashur, Sariel Har-Peled

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study colored coverage and clustering problems. Here, we are given a colored point set, where the points are covered by k (unknown) 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 oracle 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 and covering of points by k monochromatic balls.

Original languageEnglish (US)
Title of host publication37th International Symposium on Computational Geometry, SoCG 2021
EditorsKevin Buchin, Eric Colin de Verdiere
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771849
StatePublished - Jun 1 2021
Event37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States
Duration: Jun 7 2021Jun 11 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference37th International Symposium on Computational Geometry, SoCG 2021
Country/TerritoryUnited States
CityVirtual, Buffalo


  • Active learning
  • Classification
  • Linear programming

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On undecided LP, clustering and active learning'. Together they form a unique fingerprint.

Cite this