{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T04:23:06Z","timestamp":1789705386405,"version":"4.0.1"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the union of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log n for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(md log m) axis-parallel boxes.<\/jats:p>\n                  <jats:p>Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, any discretized geometric concept generated from any number of halfspaces with any number of known (to the learner) slopes in a constant dimensional space. In particular, our algorithm exactly learns (from equivalence queries only) unions of discretized axis-parallel boxes in constant dimensional space in polynomial time. Furthermore, this equivalence query only algorithm can be modified to handle a polynomial number of lies in the counterexamples provided by the environment.<\/jats:p>\n                  <jats:p>Finally, we introduce a new complexity measure that better captures the complexity of the union of m boxes than simply the number of boxes and the dimension. Our new measure, $\\sigma$, is the number of segments in the target, where a segment is a maximum portion of one of the sides of the target that lies entirely inside or entirely outside each of the other halfspaces defining the target. We present a modification of our first algorithm that uses time and queries polynomial in $\\sigma$ and log n. In fact, the time and queries (both membership and equivalence) used by this single algorithm are polynomial for eitherm or d constant.<\/jats:p>","DOI":"10.1137\/s0097539794274246","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"674-699","source":"Crossref","is-referenced-by-count":14,"title":["Exact Learning of Discretized Geometric Concepts"],"prefix":"10.1137","volume":"28","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sally A.","family":"Goldman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H. David","family":"Mathias","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116828"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"D. Angluin and M. Krikis,\n                      Learning with malicious membership queries and exceptions\n                      , in Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994, pp. 57\u201366.","DOI":"10.1145\/180139.181015"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116829"},{"key":"R4","unstructured":"E. Arkin, P. Belleville, J. Mitchell, D. Mount, K. Romanik, S. Salzberg, and D. Souvaine,\n                      Testing simple polygons\n                      , in Proceedings of the 5th Canadian Conference on Computational Geometry, 1993, pp. 387\u2013392."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"E. Arkin, H. Meijer, J. Mitchell, D. Rappaport, and S. Skiena,\n                      Decision trees for geometric models\n                      , in Proceedings of the 9th Annual Symposium on Computational Geometry, 1993, pp. 369\u2013378.","DOI":"10.1145\/160985.161167"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"P. Auer,\n                      On\u2010line learning of rectangles in noisy environments\n                      , in Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993, pp. 253\u2013261.","DOI":"10.1145\/168304.168345"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90022-X"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979223455X"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1075"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"R11","unstructured":"N. Bshouty, Personal communication, University of Calgary, 1994."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"N. Bshouty, Z. Chen, and S. Homer,\n                      On learning discretized geometric concepts\n                      , in 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 54\u201363.","DOI":"10.1109\/SFCS.1994.365705"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0021"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"W. J. Bultman and W. Maass,\n                      Fast identification of geometric objects with membership queries\n                      , in Proc. 4th Annual Workshop on Computational Learning Theory, San Mateo, CA, Morgan Kaufmann, 1991, pp. 337\u2013353.","DOI":"10.1016\/B978-1-55860-213-7.50034-1"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Z. Chen,\n                      Learning unions of two rectangles in the plane with equivalence queries\n                      , in Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, ACM Press, 1993, pp. 243\u2013252.","DOI":"10.1145\/168304.168342"},{"key":"R16","unstructured":"Z. Chen and S. Homer,\n                      The Bounded Injury Priority Method and the Learnability of Inions of Rectangles\n                      , unpublished manuscript, 1994."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993471"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. C. Culberson and R. A. Reckhow,\n                      Covering polygons is hard\n                      , in 29th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 601\u2013611.","DOI":"10.1109\/SFCS.1988.21976"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0035"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"P. W. Goldberg, S. A. Goldman, and H. D. Mathias,\n                      Learning unions of boxes with membership and equivalence queries\n                      , in Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994, pp. 198\u2013207.","DOI":"10.1145\/180139.181102"},{"key":"R23","unstructured":"Yan\u2010Bin Jia, Michael Erdmann, The complexity of sensing by point sampling, A K Peters, Wellesley, MA, 1995, 283\u201330096g:68042"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1177\/027836499601500405"},{"key":"R25","unstructured":"S. Homer and Z. Chen,\n                      Fast Learning Unions of Rectangles with Queries\n                      , unpublished manuscript, 1993."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0222052"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"P. D. Laird,\n                      Learning from Good and Bad Data\n                      , Kluwer International Series in Engineering and Computer Science, Kluwer Academic Publishers, Boston, 1988.","DOI":"10.1007\/978-1-4613-1685-5"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"P. M. Long and M. K. Warmuth,\n                      Composite geometric concepts and polynomial predictability\n                      , in Proceedings of the Third Annual Workshop on Computational Learning Theory, Morgan Kaufmann, 1990, pp. 273\u2013287.","DOI":"10.1016\/B978-1-55860-146-8.50024-2"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"W. Maass and G. Tur\u00e1n,\n                      On the complexity of learning from counterexamples\n                      , in 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 262\u2013267.","DOI":"10.1109\/SFCS.1989.63488"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992674"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993976"},{"key":"R33","unstructured":"Wolfgang Maass, Gy\u00f6rgy Tur\u00e1n, How fast can a threshold gate learn? Bradford Book, MIT Press, Cambridge, MA, 1994, 381\u201341496g:68111"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"W. Maass and M. Warmuth,\n                      Efficient learning with virtual threshold gates\n                      , in Proceedings of the 12th International Conference on Machine Learning, Morgan Kaufmann, 1995, pp. 378\u2013386.","DOI":"10.1016\/B978-1-55860-377-6.50054-2"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90005-1"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553911"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00016-6"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794274246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:52Z","timestamp":1787336572000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794274246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794274246"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794274246","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}