Home Bookmarks Papers Blog

# Active Learning a Convex Body in Low Dimensions

Sariel Har-Peled, Mitchell Jones, and Saladi Rahul.
Consider a set $\PS \subseteq \Re^d$ of $n$ points, and a convex body $\body$ provided via a separation oracle. The task at hand is to decide for each point of $\PS$ if it is in $\body$ using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using $O( \indexX{\PS} \log n)$ queries, where $\indexX{\PS}$ is the largest subset of points of $\PS$ in convex position. Furthermore, we show that in two dimensions one can solve this problem using $O( \priceY{\PS}{\body} \log^2 n )$ oracle queries, where $\priceY{\PS}{\body}$ is a lower bound on the minimum number of queries that any algorithm for this specific instance requires.
PDF. : arXiv : DBLP.