{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,17]],"date-time":"2025-03-17T15:40:03Z","timestamp":1742226003564,"version":"3.38.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T00:00:00Z","timestamp":1712448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T00:00:00Z","timestamp":1712448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-18-14493","CCF-20-07556","CCF-1907400"],"award-info":[{"award-number":["IIS-18-14493","CCF-20-07556","CCF-1907400"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,4]]},"DOI":"10.1007\/s00454-024-00637-x","type":"journal-article","created":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T19:01:37Z","timestamp":1712516497000},"page":"674-701","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Instance-Optimal Kernels in Two Dimensions"],"prefix":"10.1007","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2638-9635","authenticated-orcid":false,"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,7]]},"reference":[{"key":"637_CR1","unstructured":"Agarwal, P.K., Har-Peled, S.: Computing instance-optimal kernels in two dimensions. Proc. 29th Int. Symp. Comput. Geom. 2023, pp. 4:1\u20134:15 (2023)"},{"key":"637_CR2","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. Assoc. Comput. Mach 51(4), 606\u2013635 (2004). https:\/\/doi.org\/10.1145\/1008731.1008736http:\/\/www.acm.org\/jacm\/","DOI":"10.1145\/1008731.1008736"},{"key":"637_CR3","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Goodman, J.E., Pollack, R., Welzl, E. (eds.) Combinatorial and Computational Geometry, pp. 1\u201330. Cambridge University Press, Cambridge, UK (2005)"},{"key":"637_CR4","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Kumar, N., Sintos, S., Suri, S.: Efficient algorithms for $$k$$-regret minimizing sets. In: Iliopoulos, C.S., Pissis, S.P., Puglisi, S.J., Raman, R. (eds.) 16th Int. Symp. Exper. Alg., (SEA), pp. 7\u20131723 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2017.7. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7632\/","DOI":"10.4230\/LIPIcs.SEA.2017.7"},{"key":"637_CR5","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Yu, H.: A space-optimal data-stream algorithm for coresets in the plane. In: Erickson, J. (ed.) Proc. 23rd Annu. Sympos. Comput. Geom. pp. 1\u201310. ACM, New York, NY, USA (2007). https:\/\/doi.org\/10.1145\/1247069.1247071","DOI":"10.1145\/1247069.1247071"},{"issue":"1\u20133","key":"637_CR6","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00454-007-9013-2","volume":"39","author":"PK Agarwal","year":"2008","unstructured":"Agarwal, P.K., Har-Peled, S., Yu, H.: Robust shape fitting via peeling and grating coresets. Discret. Comput. Geom. 39(1\u20133), 38\u201358 (2008). https:\/\/doi.org\/10.1007\/s00454-007-9013-2","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"637_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/3302249","volume":"15","author":"A Blum","year":"2019","unstructured":"Blum, A., Har-Peled, S., Raichel, B.: Sparse approximation via generating point sets. ACM Trans. Algo. 15(3), 32\u201313216 (2019). https:\/\/doi.org\/10.1145\/3302249","journal-title":"ACM Trans. Algo."},{"key":"637_CR8","doi-asserted-by":"publisher","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite vc-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995). https:\/\/doi.org\/10.1007\/BF02570718","DOI":"10.1007\/BF02570718"},{"key":"637_CR9","doi-asserted-by":"publisher","unstructured":"Cao, W., Li, J., Wang, H., Wang, K., Wang, R., Wong, R.C., Zhan, W.: k-regret minimizing set: Efficient algorithms and hardness. In: 20th Int. Conf. Data. Theory, pp. 11\u201311119 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2017.11","DOI":"10.4230\/LIPIcs.ICDT.2017.11"},{"key":"637_CR10","unstructured":"Chan, T.M., Har-Peled, S., Jones, M.: Optimal algorithms for geometric centers and depth. CoRR abs\/1912.01639 (2021). arXiv:1912.01639 [cs.CG]"},{"issue":"1\u20132","key":"637_CR11","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.comgeo.2005.10.002","volume":"35","author":"TM Chan","year":"2006","unstructured":"Chan, T.M.: Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom. Theory Appl. 35(1\u20132), 20\u201335 (2006). https:\/\/doi.org\/10.1016\/j.comgeo.2005.10.002","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"637_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01840441","volume":"1","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: II. applications. Algorithmica 1(2), 163\u2013191 (1986). https:\/\/doi.org\/10.1007\/BF01840441","journal-title":"Algorithmica"},{"key":"637_CR13","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B., Guibas, L.J.: Visibility and intersection problems in plane geometry. Discret. Comput. Geom. 4, 551\u2013581 (1989). https:\/\/doi.org\/10.1007\/BF02187747","journal-title":"Discret. Comput. Geom."},{"key":"637_CR14","doi-asserted-by":"publisher","unstructured":"Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Dehne, F.K.H.A., Sack, J., Santoro, N., Whitesides, S. (eds.) Proc. 3th Workshop Algorithms Data Struct. Lect. Notes in Comp. Sci., vol. 709, pp. 246\u2013252. Springer, Berlin (1993). https:\/\/doi.org\/10.1007\/3-540-57155-8_252","DOI":"10.1007\/3-540-57155-8_252"},{"key":"637_CR15","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge, MA (2009). http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"key":"637_CR16","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0925-7721(97)00006-0","volume":"8","author":"G Das","year":"1997","unstructured":"Das, G., Goodrich, M.T.: On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees. Comput. Geom. 8, 123\u2013137 (1997). https:\/\/doi.org\/10.1016\/S0925-7721(97)00006-0","journal-title":"Comput. Geom."},{"key":"637_CR17","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd Edition. Springer, Berlin, Germany (2008). https:\/\/www.worldcat.org\/oclc\/227584184","DOI":"10.1007\/978-3-540-77974-2"},{"key":"637_CR18","doi-asserted-by":"publisher","unstructured":"Ghosh, S.K., Maheshwari,A.: An optimal algorithm for computing a minimum nested nonconvex polygon. Inform. Process. Lett. 36(6), 277\u2013280 (1990). https:\/\/doi.org\/10.1016\/0020-0190(90)90038-Y","DOI":"10.1016\/0020-0190(90)90038-Y"},{"issue":"04","key":"637_CR19","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1142\/S0218195993000257","volume":"3","author":"LJ Guibas","year":"1993","unstructured":"Guibas, L.J., Hershberger, J., Mitchell, J.S.B., Snoeyink, J.: Approximating polygons and subdivisions with minimum-link paths. Int. J. Comput. Geom. Appl. 3(04), 383\u2013415 (1993). https:\/\/doi.org\/10.1142\/S0218195993000257","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"637_CR20","doi-asserted-by":"publisher","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Math. Surveys & Monographs, vol. 173. Amer. Math. Soc., Boston, MA, USA (2011). https:\/\/doi.org\/10.1090\/surv\/173. http:\/\/sarielhp.org\/book\/","DOI":"10.1090\/surv\/173"},{"issue":"3","key":"637_CR21","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1006\/jagm.1995.1017","volume":"18","author":"J Hershberger","year":"1995","unstructured":"Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: Shoot a ray, take a walk. J. Algorithms 18(3), 403\u2013431 (1995). https:\/\/doi.org\/10.1006\/jagm.1995.1017","journal-title":"J. Algorithms"},{"issue":"3","key":"637_CR22","first-page":"159","volume":"9","author":"H Imai","year":"1986","unstructured":"Imai, H., Iri, M.: An optimal algorithm for approximating a piecewise linear function. J. Info. Process. 9(3), 159\u2013162 (1986)","journal-title":"J. Info. Process."},{"key":"637_CR23","doi-asserted-by":"publisher","unstructured":"Klimenko, G., Raichel, B.: Fast and exact convex hull simplification. In: Bojanczyk, M., Chekuri, C. (eds.) Proc. 41th Conf. Found. Soft. Tech. Theoret. Comput. LIPIcs, vol. 213, pp. 26\u201312617. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2021.26","DOI":"10.4230\/LIPIcs.FSTTCS.2021.26"},{"issue":"2","key":"637_CR24","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(84)90033-4","volume":"18","author":"CC Lee","year":"1984","unstructured":"Lee, C.C., Lee, D.T.: On a circle-cover minimization problem. Inf. Process. Lett. 18(2), 109\u2013115 (1984). https:\/\/doi.org\/10.1016\/0020-0190(84)90033-4","journal-title":"Inf. Process. Lett."},{"issue":"3\u20134","key":"637_CR25","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.ipl.2008.02.007","volume":"107","author":"JS Mitchell","year":"2008","unstructured":"Mitchell, J.S., Polishchuk, V.: Minimum-perimeter enclosures. Inform. Process. Lett. 107(3\u20134), 120\u2013124 (2008). https:\/\/doi.org\/10.1016\/j.ipl.2008.02.007","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"637_CR26","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0925-7721(95)00006-U","volume":"5","author":"JS Mitchell","year":"1995","unstructured":"Mitchell, J.S., Suri, S.: Separation and approximation of polyhedral objects. Comput. Geom. Theory Appl. 5(2), 95\u2013114 (1995). https:\/\/doi.org\/10.1016\/0925-7721(95)00006-U","journal-title":"Comput. Geom. Theory Appl."},{"key":"637_CR27","doi-asserted-by":"crossref","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry - An Introduction. Springer, New York, NY (1985)","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"637_CR28","unstructured":"Schlag, M., Luccio, F., Maestrini, P., Lee, D.T., Wong, C.K.: A visibility problem in VLSI layout compaction. In: Preparata, F.P. (ed.) Advances in Computing Research, Volume 2: VLSI Theory, pp. 259\u2013282. JAI Press Inc., Greenwich, CT (1984)"},{"key":"637_CR29","doi-asserted-by":"publisher","unstructured":"Wang, C.A., Chan, E.P.F.: Finding the minimum visible vertex distance between two non-intersecting simple polygons. In: Aggarwal, A. (ed.) Proc. 2nd Annu. Sympos. Comput. Geom., pp. 34\u201342. ACM, New York, NY, USA (1986). https:\/\/doi.org\/10.1145\/10515.10519","DOI":"10.1145\/10515.10519"},{"key":"637_CR30","doi-asserted-by":"publisher","unstructured":"Wang, Y., Mathioudakis, M., Li, Y., Tan, K.: Minimum coresets for maxima representation of multidimensional data. In: Libkin, L., Pichler, R., Guagliardo, P. (eds.) Proc. 40th Symp. Principles Database Sys., pp. 138\u2013152. ACM, New York, NY, USA (2021). https:\/\/doi.org\/10.1145\/3452021.3458322","DOI":"10.1145\/3452021.3458322"},{"issue":"2","key":"637_CR31","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/bf01931283","volume":"31","author":"CA Wang","year":"1991","unstructured":"Wang, C.A.: Finding minimal nested polygons. BIT Numerical Mathematics 31(2), 230\u2013236 (1991). https:\/\/doi.org\/10.1007\/bf01931283","journal-title":"BIT Numerical Mathematics"},{"key":"637_CR32","doi-asserted-by":"publisher","unstructured":"Yu, H., Agarwal, P.K., Poreddy, R., Varadarajan, K.R.: Practical methods for shape fitting and kinetic data structures using coresets. Algorithmica 52(3), 378\u2013402 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9067-9","DOI":"10.1007\/s00453-007-9067-9"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00637-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00637-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00637-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,17]],"date-time":"2025-03-17T14:58:00Z","timestamp":1742223480000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00637-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,7]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["637"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00637-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,4,7]]},"assertion":[{"value":"13 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}