Active-Learning a Convex Body in Low Dimensions

Sariel Har-Peled, Mitchell Jones, Saladi Rahul

Research output: Contribution to journalArticlepeer-review

Abstract

Consider a set P⊆ Rd of n points, and a convex body C provided via a separation oracle. The task at hand is to decide for each point of P if it is in C using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using [InlineEquation not available: see fulltext.] queries, where [InlineEquation not available: see fulltext.] is the size of the largest subset of points of P in convex position. In 2D, we provide an algorithm that efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using [InlineEquation not available: see fulltext.] oracle queries, where [InlineEquation not available: see fulltext.] is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if C contains all points of P. As an application of the above, we show that the discrete geometric median of a point set P in R2 can be computed in [InlineEquation not available: see fulltext.] expected time.

Original languageEnglish (US)
JournalAlgorithmica
DOIs
StateAccepted/In press - 2021

Keywords

  • Active learning
  • Approximation algorithms
  • Computational geometry
  • Separation oracles

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Active-Learning a Convex Body in Low Dimensions'. Together they form a unique fingerprint.

Cite this