TY - JOUR

T1 - Active-Learning a Convex Body in Low Dimensions

AU - Har-Peled, Sariel

AU - Jones, Mitchell

AU - Rahul, Saladi

N1 - Funding Information:
Sariel Har-Peled is supported in part by NSF AF Award CCF-1907400.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.

PY - 2021/6

Y1 - 2021/6

N2 - 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.

AB - 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.

KW - Active learning

KW - Approximation algorithms

KW - Computational geometry

KW - Separation oracles

UR - http://www.scopus.com/inward/record.url?scp=85101862202&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85101862202&partnerID=8YFLogxK

U2 - 10.1007/s00453-021-00807-w

DO - 10.1007/s00453-021-00807-w

M3 - Article

AN - SCOPUS:85101862202

VL - 83

SP - 1885

EP - 1917

JO - Algorithmica (New York)

JF - Algorithmica (New York)

SN - 0178-4617

IS - 6

ER -