{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:45:48Z","timestamp":1770972348761,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,4,7]],"date-time":"2021-04-07T00:00:00Z","timestamp":1617753600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,7]],"date-time":"2021-04-07T00:00:00Z","timestamp":1617753600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s00453-021-00825-8","type":"journal-article","created":{"date-parts":[[2021,4,7]],"date-time":"2021-04-07T19:04:42Z","timestamp":1617822282000},"page":"2273-2302","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Minimum Consistent Subset Problem"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6396-4494","authenticated-orcid":false,"given":"Ahmad","family":"Biniaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paz","family":"Carmi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Lou","family":"De Carufel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saeed","family":"Mehrabi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,7]]},"reference":[{"key":"825_CR1","doi-asserted-by":"crossref","unstructured":"Banerjee, S., Bhore, S., Chitnis, R.: Algorithms and hardness results for nearest neighbor problems in bicolored point sets. In: Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN), pp. 80\u201393 (2018)","DOI":"10.1007\/978-3-319-77404-6_7"},{"key":"825_CR2","doi-asserted-by":"crossref","unstructured":"Bhattacharya, B.K., Bishnu, A., Cheong, O., Das, S., Karmakar, A., Snoeyink, J.: Computation of non-dominated points using compact Voronoi diagrams. In: Proceedings of the 4th International Workshop on Algorithms and Computation (WALCOM), pp. 82\u201393 (2010)","DOI":"10.1007\/978-3-642-11440-3_8"},{"issue":"3","key":"825_CR3","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."},{"issue":"3","key":"825_CR4","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. Inf. Theory 18(3), 431\u2013433 (1972)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"825_CR5","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. Inf. Theory 64(6), 4120\u20134128 (2018). Also in NIPS 2014","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"825_CR6","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. Inf. Theory 14(3), 515\u2013516 (1968)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"825_CR7","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":"825_CR8","doi-asserted-by":"crossref","unstructured":"Khodamoradi, K., Krishnamurti, R., Roy, B.: Consistent subset problem with two labels. In: Proceedings of the 4th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), pp. 131\u2013142 (2018)","DOI":"10.1007\/978-3-319-74180-2_11"},{"issue":"4","key":"825_CR9","doi-asserted-by":"publisher","first-page":"353","DOI":"10.3233\/FI-1995-2243","volume":"22","author":"DG Kirkpatrick","year":"1995","unstructured":"Kirkpatrick, D.G., Snoeyink, J.: Tentative prune-and-search for computing fixed-points with applications to geometric computation. Fundamenta Informaticae 22(4), 353\u2013370 (1995). Also in SoCG 1993","journal-title":"Fundamenta Informaticae"},{"key":"825_CR10","doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In: Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), pp. 865\u2013877 (2015). Full version in arXiv:1504.05476","DOI":"10.1007\/978-3-662-48350-3_72"},{"issue":"2","key":"825_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. Sect. E E64(2), 57\u201364 (1981)","journal-title":"Trans. Inst. Electron. Commun. Eng. Jpn. Sect. E"},{"issue":"1","key":"825_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF02716580","volume":"15","author":"M McAllister","year":"1996","unstructured":"McAllister, M., Kirkpatrick, D.G., Snoeyink, J.: A compact piecewise-linear Voronoi diagram for convex sites in the plane. Discret. Comput. Geom. 15(1), 73\u2013105 (1996). Also in FOCS 1993","journal-title":"Discret. Comput. Geom."},{"issue":"1","key":"825_CR13","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31(1), 114\u2013127 (1984)","journal-title":"J. ACM"},{"issue":"3","key":"825_CR14","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"GL Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265\u2013279 (1986). Also in STOC 1984","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"825_CR15","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. Inf. Theory 21(6), 665\u2013669 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"825_CR16","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science (FOCS), pp. 151\u2013162 (1975)","DOI":"10.1109\/SFCS.1975.8"},{"issue":"4","key":"825_CR17","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":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00825-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00825-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00825-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T09:08:35Z","timestamp":1624352915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00825-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,7]]},"references-count":17,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["825"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00825-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,7]]},"assertion":[{"value":"22 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}