TY - GEN
T1 - Active learning a convex body in low dimensions
AU - Har-Peled, Sariel
AU - Jones, Mitchell
AU - Rahul, Saladi
N1 - Publisher Copyright:
© Sariel Har-Peled, Mitchell Jones, and Saladi Rahul; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
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 -