Active learning a convex body in low dimensions

Sariel Har-Peled, Mitchell Jones, Saladi Rahul

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

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 O(9P log n) queries, where 9P is the largest subset of points of P in convex position. In 2D, we provide an algorithm which efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using O(☉(P, C) log2 n) oracle queries, where ☉(P, C) 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 O(n log2 n (log n log log n + 9P )) expected time.

Original languageEnglish (US)
Title of host publication47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
EditorsArtur Czumaj, Anuj Dawar, Emanuela Merelli
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771382
DOIs
StatePublished - Jun 1 2020
Event47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 - Virtual, Online, Germany
Duration: Jul 8 2020Jul 11 2020

Publication series

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

Conference

Conference47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
CountryGermany
CityVirtual, Online
Period7/8/207/11/20

Keywords

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

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Active learning a convex body in low dimensions'. Together they form a unique fingerprint.

Cite this