# Active Learning a Convex Body in Low Dimensions

arXiv: https://arxiv.org/abs/1903.03693 · HTML: https://mlsanity.com/paper/1903.03693/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2019.

## Built on by (most cited first, 3 of 3)

- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Active Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2201.09433/) (2022)

## Abstract (arXiv)

Consider a set P subseteq Red 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( h(P) log n) queries, where h(P) is the largest subset of points of P in convex position. Furthermore, we show that in two dimensions one can solve this problem using O( v(P,C) log2 n ) oracle queries, where v(P, C) is a lower bound on the minimum number of queries that any algorithm for this specific instance requires.