Active-Learning a Convex Body in Low Dimensions

Consider a set P⊆ R^d 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 R² can be computed in [InlineEquation not available: see fulltext.] expected time.