{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:37Z","timestamp":1740109297400,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1907400"],"award-info":[{"award-number":["CCF-1907400"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00453-021-00807-w","type":"journal-article","created":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T05:02:52Z","timestamp":1614574972000},"page":"1885-1917","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Active-Learning a Convex Body in Low Dimensions"],"prefix":"10.1007","volume":"83","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2971-398X","authenticated-orcid":false,"given":"Mitchell","family":"Jones","sequence":"additional","affiliation":[]},{"given":"Saladi","family":"Rahul","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,1]]},"reference":[{"issue":"2","key":"807_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1002\/rsa.20269","volume":"35","author":"G Ambrus","year":"2009","unstructured":"Ambrus, G., B\u00e1r\u00e1ny, I.: Longest convex chains. Rand. Struct. Algorithm 35(2), 137\u2013162 (2009). https:\/\/doi.org\/10.1002\/rsa.20269","journal-title":"Rand. Struct. Algorithm"},{"issue":"4","key":"807_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF00116828","volume":"2","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1987). https:\/\/doi.org\/10.1007\/BF00116828","journal-title":"Mach. Learn."},{"issue":"2\u20133","key":"807_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(82)90115-7","volume":"40","author":"I B\u00e1r\u00e1ny","year":"1982","unstructured":"B\u00e1r\u00e1ny, I.: A generalization of Carath\u00e9odory\u2019s theorem. Discrete Math. 40(2\u20133), 141\u2013152 (1982). https:\/\/doi.org\/10.1016\/0012-365X(82)90115-7","journal-title":"Discrete Math."},{"key":"807_CR4","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF02187886","volume":"2","author":"I B\u00e1r\u00e1ny","year":"1987","unstructured":"B\u00e1r\u00e1ny, I., F\u00fcredi, Z.: Computing the volume is difficulte. Discrete Comput. Geom. 2, 319\u2013326 (1987). https:\/\/doi.org\/10.1007\/BF02187886","journal-title":"Discrete Comput. Geom."},{"key":"807_CR5","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: J.I. Munro (ed.) Proceedings of 15th ACM-SIAM Symposium Discrete Algs. (SODA), pp. 430\u2013436. SIAM (2004). URL http:\/\/dl.acm.org\/citation.cfm?id=982792.982853"},{"key":"807_CR6","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387\u2013421 (1989). https:\/\/doi.org\/10.1007\/BF02187740","journal-title":"Discrete Comput. Geom."},{"key":"807_CR7","doi-asserted-by":"publisher","unstructured":"Cohen, M.B., Lee, Y.T., Miller, G.L., Pachocki, J., Sidford, A.: Geometric median in nearly linear time. In: D. Wichs, Y. Mansour (eds.) Proc. 48th ACM Sympos. Theory Comput. (STOC), pp. 9\u201321. ACM (2016). https:\/\/doi.org\/10.1145\/2897518.2897647","DOI":"10.1145\/2897518.2897647"},{"issue":"2","key":"807_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF00993277","volume":"15","author":"DA Cohn","year":"1994","unstructured":"Cohn, D.A., Atlas, L.E., Ladner, R.E.: Improving generalization with active learning. Mach. Learn. 15(2), 201\u2013221 (1994). https:\/\/doi.org\/10.1007\/BF00993277","journal-title":"Mach. Learn."},{"issue":"3","key":"807_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0021-9045(74)90120-8","volume":"10","author":"RM Dudley","year":"1974","unstructured":"Dudley, R.M.: Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory 10(3), 227\u2013236 (1974). https:\/\/doi.org\/10.1016\/0021-9045(74)90120-8","journal-title":"J. Approx. Theory"},{"issue":"4","key":"807_CR10","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/s00454-018-0043-8","volume":"61","author":"E Ezra","year":"2019","unstructured":"Ezra, E., Sharir, M.: A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. Discrete Comput. Geom. 61(4), 735\u2013755 (2019). https:\/\/doi.org\/10.1007\/s00454-018-0043-8","journal-title":"Discrete Comput. Geom."},{"key":"807_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/C2013-0-15234-8","volume-title":"An Introduction to Nonsmooth Analysis","author":"J Ferrera","year":"2013","unstructured":"Ferrera, J.: An Introduction to Nonsmooth Analysis. Academic Press, Boston (2013). https:\/\/doi.org\/10.1016\/C2013-0-15234-8"},{"key":"807_CR12","unstructured":"Guo, Y., Greiner, R.: Optimistic active-learning using mutual information. In: Proceedings of 20th International Joint Conference on AI (IJCAI), pp. 823\u2013829 (2007). URL http:\/\/ijcai.org\/Proceedings\/07\/Papers\/132.pdf"},{"key":"807_CR13","unstructured":"Har-Peled, S., Jones, M., Rahul, S.: An animation of the greedy classification algorithm in 2d. URL https:\/\/www.youtube.com\/watch?v=IZX0VQdIgNA"},{"key":"807_CR14","doi-asserted-by":"publisher","unstructured":"Har-Peled, S., Jones, M., Rahul, S.: Active learning a convex body in low dimensions. In: A. Czumaj, A. Dawar, E. Merelli (eds.) Proc. 47th Int. Colloq. Automata Lang. Prog. (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), vol. 168, pp. 64:1\u201364:17. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.64. URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/12471","DOI":"10.4230\/LIPIcs.ICALP.2020.64"},{"issue":"2","key":"807_CR15","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00454-016-9801-7","volume":"56","author":"S Har-Peled","year":"2016","unstructured":"Har-Peled, S., Kumar, N., Mount, D.M., Raichel, B.: Space exploration via proximity search. Discrete Comput. Geom. 56(2), 357\u2013376 (2016). https:\/\/doi.org\/10.1007\/s00454-016-9801-7","journal-title":"Discrete Comput. Geom."},{"key":"807_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987). https:\/\/doi.org\/10.1007\/BF02187876","journal-title":"Discrete Comput. Geom."},{"key":"807_CR17","doi-asserted-by":"publisher","unstructured":"Kane, D.M., Lovett, S., Moran, S., Zhang, J.: Active classification with comparison queries. In: Proc. 58th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 355\u2013366 (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.40","DOI":"10.1109\/FOCS.2017.40"},{"issue":"1","key":"807_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1(1), 59\u201371 (1986). https:\/\/doi.org\/10.1007\/BF02187683","journal-title":"Discrete Comput. Geom."},{"key":"807_CR19","unstructured":"Kupavskii, A.: The vc-dimension of k-vertex d-polytopes. CoRR arXiv:abs\/2004.04841 (2020)"},{"key":"807_CR20","doi-asserted-by":"publisher","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry, Grad. Text in Math., vol. 212. Springer (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7\/. URL http:\/\/kam.mff.cuni.cz\/~matousek\/dg.html","DOI":"10.1007\/978-1-4613-0039-7\/"},{"key":"807_CR21","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Wagner, U.: New constructions of weak epsilon-nets. In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 129\u2013135. ACM (2003)","DOI":"10.1145\/777792.777813"},{"issue":"2","key":"807_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Dynamic fractional cascading. Algorithmica 5(2), 215\u2013241 (1990). https:\/\/doi.org\/10.1007\/BF01840386","journal-title":"Algorithmica"},{"key":"807_CR23","doi-asserted-by":"publisher","unstructured":"Panahi, F., Adler, A., van der Stappen, A.F., Goldberg, K.: An efficient proximity probing algorithm for metrology. In: Int. Conf. on Automation Science and Engineering, CASE 2013, pp. 342\u2013349 (2013). https:\/\/doi.org\/10.1109\/CoASE.2013.6653995","DOI":"10.1109\/CoASE.2013.6653995"},{"key":"807_CR24","doi-asserted-by":"publisher","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer (1985). https:\/\/doi.org\/10.1007\/978-1-4612-1098-6","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"807_CR25","doi-asserted-by":"publisher","unstructured":"Rubin, N.: An improved bound for weak epsilon-nets in the plane. In: M.\u00a0Thorup (ed.) Proc. 59th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 224\u2013235. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00030","DOI":"10.1109\/FOCS.2018.00030"},{"key":"807_CR26","unstructured":"Settles, B.: Active learning literature survey. Tech. Rep. #1648, Computer Science, Univ. Wisconsin, Madison (2009). URL https:\/\/minds.wisconsin.edu\/bitstream\/handle\/1793\/60660\/TR1648.pdf?sequence=1&isAllowed=y"},{"key":"807_CR27","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."},{"key":"807_CR28","doi-asserted-by":"publisher","unstructured":"Weil, W. (ed.): Random Polytopes, Convex Bodies, and Approximation, pp. 77\u2013118. Springer Berlin Heidelberg, Berlin, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-38175-4_2","DOI":"10.1007\/978-3-540-38175-4_2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00807-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00807-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00807-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:05:25Z","timestamp":1621937125000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00807-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,1]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["807"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00807-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,3,1]]},"assertion":[{"value":"10 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}