{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:33:05Z","timestamp":1760441585548,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_12","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"155-167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Minimum Consistent Subset Problem"],"prefix":"10.1007","author":[{"given":"Ahmad","family":"Biniaz","sequence":"first","affiliation":[]},{"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[]},{"given":"Paz","family":"Carmi","sequence":"additional","affiliation":[]},{"given":"Jean-Lou","family":"De Carufel","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"Saeed","family":"Mehrabi","sequence":"additional","affiliation":[]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-319-77404-6_7","volume-title":"LATIN 2018: Theoretical Informatics","author":"S Banerjee","year":"2018","unstructured":"Banerjee, S., Bhore, S., Chitnis, R.: Algorithms and hardness results for nearest neighbor problems in bicolored point sets. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018. LNCS, vol. 10807, pp. 80\u201393. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-77404-6_7"},{"issue":"3","key":"12_CR2","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M de Berg","year":"2012","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(3), 187\u2013206 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-642-11440-3_8","volume-title":"WALCOM: Algorithms and Computation","author":"B Bhattacharya","year":"2010","unstructured":"Bhattacharya, B., Bishnu, A., Cheong, O., Das, S., Karmakar, A., Snoeyink, J.: Computation of non-dominated points using compact Voronoi diagrams. In: Rahman, M.S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 82\u201393. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11440-3_8"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Biniaz, A., Cabello, S., Carmi, P., De Carufel, J.-L., Maheshwari, A., Mehrabi, S., Smid, M.: On the minimum consistent subset problem (2018). http:\/\/arxiv.org\/abs\/1810.09232","DOI":"10.1007\/978-3-030-24766-9_12"},{"issue":"3","key":"12_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1109\/TIT.1972.1054809","volume":"18","author":"G Gates","year":"1972","unstructured":"Gates, G.: The reduced nearest neighbor rule. IEEE Trans. Inform. Theory 18(3), 431\u2013433 (1972)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"6","key":"12_CR6","doi-asserted-by":"publisher","first-page":"4120","DOI":"10.1109\/TIT.2018.2822267","volume":"64","author":"L Gottlieb","year":"2018","unstructured":"Gottlieb, L., Kontorovich, A., Nisnevitch, P.: Near-optimal sample compression for nearest neighbors. IEEE Trans. Inform. Theory 64(6), 4120\u20134128 (2018). Also in NIPS 2014","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"3","key":"12_CR7","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TIT.1968.1054155","volume":"14","author":"PE Hart","year":"1968","unstructured":"Hart, P.E.: The condensed nearest neighbor rule. IEEE Trans. Inform. Theory 14(3), 515\u2013516 (1968)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1","key":"12_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01185335","volume":"9","author":"RZ Hwang","year":"1993","unstructured":"Hwang, R.Z., Lee, R.C.T., Chang, R.C.: The slab dividing approach to solve the Euclidean $$p$$-center problem. Algorithmica 9(1), 1\u201322 (1993)","journal-title":"Algorithmica"},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-319-74180-2_11","volume-title":"Algorithms and Discrete Applied Mathematics","author":"K Khodamoradi","year":"2018","unstructured":"Khodamoradi, K., Krishnamurti, R., Roy, B.: Consistent subset problem with two labels. In: Panda, B.S., Goswami, P.P. (eds.) CALDAM 2018. LNCS, vol. 10743, pp. 131\u2013142. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-74180-2_11"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1007\/978-3-662-48350-3_72","volume-title":"Algorithms - ESA 2015","author":"D Marx","year":"2015","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 865\u2013877. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72. Full version in arXiv:1504.05476"},{"issue":"2","key":"12_CR11","first-page":"57","volume":"E64","author":"S Masuyama","year":"1981","unstructured":"Masuyama, S., Ibaraki, T., Hasegawa, T.: Computational complexity of the $$m$$-center problems in the plane. Trans. Inst. Electron. Commun. Eng. Jpn. Section E E64(2), 57\u201364 (1981)","journal-title":"Trans. Inst. Electron. Commun. Eng. Jpn. Section E"},{"issue":"6","key":"12_CR12","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1109\/TIT.1975.1055464","volume":"21","author":"G Ritter","year":"1975","unstructured":"Ritter, G., Woodruff, H., Lowry, S., Isenhour, T.: An algorithm for a selective nearest neighbor decision rule. IEEE Trans. Inform. Theory 21(6), 665\u2013669 (1975)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1142\/S0218195992000226","volume":"2","author":"GT Wilfong","year":"1992","unstructured":"Wilfong, G.T.: Nearest neighbor problems. Int. J. Comput. Geom. Appl. 2(4), 383\u2013416 (1992). Also in SoCG 1991","journal-title":"Int. J. Comput. Geom. Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24766-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:53:20Z","timestamp":1710266000000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}