{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T23:09:08Z","timestamp":1768518548284,"version":"3.49.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T00:00:00Z","timestamp":1668384000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T00:00:00Z","timestamp":1668384000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1421231"],"award-info":[{"award-number":["1421231"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1907400"],"award-info":[{"award-number":["1907400"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1217462"],"award-info":[{"award-number":["1217462"]}],"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":[[2023,4]]},"DOI":"10.1007\/s00453-022-01059-y","type":"journal-article","created":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T12:03:01Z","timestamp":1668427381000},"page":"965-975","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Few Cuts Meet Many Point Sets"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2638-9635","authenticated-orcid":false,"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitchell","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,14]]},"reference":[{"issue":"1","key":"1059_CR1","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00454-015-9701-2","volume":"54","author":"J Matousek","year":"2015","unstructured":"Matousek, J., Pat\u00e1kov\u00e1, Z.: Multilevel polynomial partitions and simplified range searching. Disc. Comput. Geom. 54(1), 22\u201341 (2015). https:\/\/doi.org\/10.1007\/s00454-015-9701-2","journal-title":"Disc. Comput. Geom."},{"issue":"2","key":"1059_CR2","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/19M1268550","volume":"50","author":"PK Agarwal","year":"2021","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Zahl, J.: Efficient algorithm for generalized polynomial partitioning and its applications. SIAM J. Comput. 50(2), 760\u2013787 (2021). https:\/\/doi.org\/10.1137\/19M1268550","journal-title":"SIAM J. Comput."},{"key":"1059_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/9781108959988","volume-title":"Polynomial Methods and Incidence Theory","author":"A Sheffer","year":"2022","unstructured":"Sheffer, A.: Polynomial Methods and Incidence Theory. Cambridge University Press, Cambridge (2022). https:\/\/doi.org\/10.1017\/9781108959988"},{"issue":"2","key":"1059_CR4","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1215\/S0012-7094-42-00925-6","volume":"9","author":"AH Stone","year":"1942","unstructured":"Stone, A.H., Tukey, J.W.: Generalized \u201csandwich\u2019\u2019 theorems. Duke Math. J. 9(2), 356\u2013359 (1942). https:\/\/doi.org\/10.1215\/S0012-7094-42-00925-6","journal-title":"Duke Math. J."},{"issue":"3","key":"1059_CR5","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1007\/s00454-019-00103-z","volume":"63","author":"S Har-Peled","year":"2020","unstructured":"Har-Peled, S., Jones, M.: On separating points by lines. Disc. Comput. Geom. 63(3), 705\u2013730 (2020). https:\/\/doi.org\/10.1007\/s00454-019-00103-z","journal-title":"Disc. Comput. Geom."},{"key":"1059_CR6","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF02574017","volume":"11","author":"C-Y Lo","year":"1994","unstructured":"Lo, C.-Y., Matou\u0161ek, J., Steiger, W.: Algorithms for ham-sandwich cuts. Disc. Comput. Geom. 11, 433\u2013452 (1994). https:\/\/doi.org\/10.1007\/BF02574017","journal-title":"Disc. Comput. Geom."},{"issue":"1\u20133","key":"1059_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s00454-007-9021-2","volume":"39","author":"I B\u00e1r\u00e1ny","year":"2008","unstructured":"B\u00e1r\u00e1ny, I., Hubard, A., Jer\u00f3nimo, J.: Slicing convex sets and measures by a hyperplane. Disc. Comput. Geom. 39(1\u20133), 67\u201375 (2008). https:\/\/doi.org\/10.1007\/s00454-007-9021-2","journal-title":"Disc. Comput. Geom."},{"issue":"1","key":"1059_CR8","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1112\/blms.12109","volume":"50","author":"PV Blagojevi\u0107","year":"2018","unstructured":"Blagojevi\u0107, P.V., Sober\u00f3n, P.: Thieves can make sandwiches. Bull. Lond. Math. Soc. 50(1), 108\u2013123 (2018). https:\/\/doi.org\/10.1112\/blms.12109","journal-title":"Bull. Lond. Math. Soc."},{"issue":"2","key":"1059_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF02717729","volume":"15","author":"EA Ramos","year":"1996","unstructured":"Ramos, E.A.: Equipartition of mass distributions by hyperplanes. Disc. Comput. Geom. 15(2), 147\u2013167 (1996). https:\/\/doi.org\/10.1007\/BF02717729","journal-title":"Disc. Comput. Geom."},{"key":"1059_CR10","doi-asserted-by":"publisher","unstructured":"Schnider, P.: Ham-sandwich cuts and center transversals in subspaces. In: Proc. 35th Int. Annu. Sympos. Comput. Geom. (SoCG). LIPIcs, vol. 129, pp. 56\u2013 15615 ( 2019). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.56","DOI":"10.4230\/LIPIcs.SoCG.2019.56"},{"issue":"3","key":"1059_CR11","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00454-009-9225-8","volume":"44","author":"W Steiger","year":"2010","unstructured":"Steiger, W., Zhao, J.: Generalized ham-sandwich cuts. Disc. Comput. Geom. 44(3), 535\u2013545 (2010). https:\/\/doi.org\/10.1007\/s00454-009-9225-8","journal-title":"Comput. Geom."},{"issue":"3","key":"1059_CR12","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00454-012-9443-3","volume":"48","author":"H Kaplan","year":"2012","unstructured":"Kaplan, H., Matou\u0161ek, J., Sharir, M.: Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique. Disc. Comput. Geom. 48(3), 499\u2013517 (2012). https:\/\/doi.org\/10.1007\/s00454-012-9443-3","journal-title":"Disc. Comput. Geom."},{"issue":"6","key":"1059_CR13","doi-asserted-by":"publisher","first-page":"2039","DOI":"10.1137\/120890855","volume":"42","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Sharir, M.: On range searching with semialgebraic sets. II. SIAM J. Comput. 42(6), 2039\u20132062 (2013). https:\/\/doi.org\/10.1137\/120890855","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1059_CR14","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1145\/197405.197408","volume":"26","author":"J Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J.: Geometric range searching. ACM Comput. Surv. 26(4), 421\u2013461 (1994). https:\/\/doi.org\/10.1145\/197405.197408","journal-title":"ACM Comput. Surv."},{"key":"1059_CR15","doi-asserted-by":"publisher","unstructured":"Inamdar, T., Varadarajan, K.R.: On partial covering for geometric set systems. In: Speckmann, B., T\u00f3th, C.D. (eds.) Proc. 34th Int. Annu. Sympos. Comput. Geom. (SoCG). LIPIcs, vol. 99, pp. 47\u2013 14714. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Wadern, Germany ( 2018). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.47","DOI":"10.4230\/LIPIcs.SoCG.2018.47"},{"issue":"4","key":"1059_CR16","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385\u2013393 (1982). https:\/\/doi.org\/10.1007\/BF02579435","journal-title":"Combinatorica"},{"issue":"4","key":"1059_CR17","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"SG Kolliopoulos","year":"2005","unstructured":"Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering\/packing integer programs. J. Comput. Syst. Sci. 71(4), 495\u2013505 (2005). https:\/\/doi.org\/10.1016\/j.jcss.2005.05.002","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01059-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01059-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01059-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,29]],"date-time":"2023-03-29T13:12:54Z","timestamp":1680095574000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01059-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,14]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1059"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01059-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,14]]},"assertion":[{"value":"19 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}