TY - GEN

T1 - Active learning a convex body in low dimensions

AU - Har-Peled, Sariel

AU - Jones, Mitchell

AU - Rahul, Saladi

N1 - Funding Information:
Funding Sariel Har-Peled: Supported in part by NSF AF award CCF-1907400. Mitchell Jones: Supported in part by NSF AF award CCF-1907400.

PY - 2020/6/1

Y1 - 2020/6/1

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

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

KW - Active learning

KW - Approximation algorithms

KW - Computational geometry

KW - Separation oracles

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

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

U2 - 10.4230/LIPIcs.ICALP.2020.64

DO - 10.4230/LIPIcs.ICALP.2020.64

M3 - Conference contribution

AN - SCOPUS:85089346165

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

A2 - Czumaj, Artur

A2 - Dawar, Anuj

A2 - Merelli, Emanuela

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

Y2 - 8 July 2020 through 11 July 2020

ER -