{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T20:17:05Z","timestamp":1772914625257,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T00:00:00Z","timestamp":1599004800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T00:00:00Z","timestamp":1599004800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1814026"],"award-info":[{"award-number":["CCF-1814026"]}],"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":["CCF-1421231"],"award-info":[{"award-number":["CCF-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":["CCF-1907400"],"award-info":[{"award-number":["CCF-1907400"]}],"id":[{"id":"10.13039\/100000143","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":[[2021,9]]},"DOI":"10.1007\/s00454-020-00239-3","type":"journal-article","created":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T15:04:13Z","timestamp":1599059053000},"page":"769-791","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Smallest k-Enclosing Rectangle Revisited"],"prefix":"10.1007","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8093-0675","authenticated-orcid":false,"given":"Timothy M.","family":"Chan","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":[[2020,9,2]]},"reference":[{"issue":"1","key":"239_CR1","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/0196-6774(91)90022-Q","volume":"12","author":"A Aggarwal","year":"1991","unstructured":"Aggarwal, A., Imai, H., Katoh, N., Suri, S.: Finding $$k$$ points with minimum diameter and related problems. J. Algorithms 12(1), 38\u201356 (1991)","journal-title":"J. Algorithms"},{"issue":"2","key":"239_CR2","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.jda.2008.12.002","volume":"7","author":"R Atanassov","year":"2009","unstructured":"Atanassov, R., Bose, P., Couture, M., Maheshwari, A., Morin, P., Paquette, M., Smid, M., Wuhrer, S.: Algorithms for optimal outlier removal. J. Discrete Algorithms 7(2), 239\u2013248 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"239_CR3","unstructured":"Backurs, A., Dikkala, N., Tzamos, Ch.: Tight hardness results for maximum weight rectangles. In: 43rd International Colloquium on Automata, Languages, and Programming. Leibniz Int. Proc. Inform., vol.\u00a055, #\u00a081. Leibniz-Zent. Inform., Wadern (2016)"},{"key":"239_CR4","unstructured":"Barba, L., Durocher, S., Fraser, R., Hurtado, F., Mehrabi, S., Mondal, D., Morrison, J., Skala, M., Wahid, M.A.: On $$k$$-enclosing objects in a coloured point set. In: 25th Canadian Conference on Computational Geometry (Waterloo 2013), #\u00a035. Carleton University, Ottawa (2013). http:\/\/cccg.ca\/proceedings\/2013\/papers\/paper_35.pdf"},{"issue":"8","key":"239_CR5","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.ipl.2014.03.007","volume":"114","author":"J Barbay","year":"2014","unstructured":"Barbay, J., Chan, T.M., Navarro, G., P\u00e9rez-Lantero, P.: Maximum-weight planar boxes in $$O(n^2)$$ time (and better). Inf. Process. Lett. 114(8), 437\u2013445 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"239_CR6","first-page":"207","volume":"10","author":"M de Berg","year":"2019","unstructured":"de Berg, M., Cabello, S., Cheong, O., Eppstein, D., Knauer, Ch.: Covering many points with a small-area box. J. Comput. Geom. 10(1), 207\u2013222 (2019)","journal-title":"J. Comput. Geom."},{"issue":"2","key":"239_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(93)90222-U","volume":"45","author":"M Bern","year":"1993","unstructured":"Bern, M.: Approximate closest-point queries in high dimensions. Inf. Process. Lett. 45(2), 95\u201399 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"239_CR8","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/s00453-012-9734-3","volume":"69","author":"D Bremner","year":"2014","unstructured":"Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., P\u0103tra\u015fcu, M., Taslakian, P.: Necklaces, convolutions, and $$X+Y$$. Algorithmica 69(2), 294\u2013314 (2014)","journal-title":"Algorithmica"},{"key":"239_CR9","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Greve, M., L\u00f3pez-Ortiz, A.: Online sorted range reporting. In: Algorithms and Computation (Honolulu 2009). Lecture Notes in Computer Science, vol. 5878, pp. 173\u2013182. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-10631-6_19"},{"issue":"3","key":"239_CR10","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/PL00009390","volume":"20","author":"TM Chan","year":"1998","unstructured":"Chan, T.M.: Approximate nearest neighbor queries revisited. Discrete Comput. Geom. 20(3), 359\u2013373 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"239_CR11","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/PL00009478","volume":"22","author":"TM Chan","year":"1999","unstructured":"Chan, T.M.: Geometric applications of a randomized optimization technique. Discrete Comput. Geom. 22(4), 547\u2013567 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"239_CR12","unstructured":"Chan, T.M., Har-Peled, S.: Smallest $$k$$-enclosing rectangle revisited. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol.\u00a0129, #\u00a023. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"239_CR13","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Lewenstein, M.: Clustered integer 3SUM via additive combinatorics. In: 47th ACM Symposium on Theory of Computing, pp. 31\u201340. ACM, New York (2015)","DOI":"10.1145\/2746539.2746568"},{"key":"239_CR14","doi-asserted-by":"crossref","unstructured":"Chan, T.M., P\u0103tra\u015fcu, M.: Counting inversions, offline orthogonal range counting, and related problems. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 161\u2013173. SIAM, Philadelphia (2010)","DOI":"10.1137\/1.9781611973075.15"},{"key":"239_CR15","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov\u2013Smolensky. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1246\u20131255. ACM, New York (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"239_CR16","unstructured":"Cygan, M., Mucha, M., W\u0119grzycki, K., W\u0142odarczyk, M.: On problems equivalent to $$(\\min ,+)$$-convolution. In: 44th International Colloquium on Automata, Languages, and Programming. Leibniz Int. Proc. Inform., vol.\u00a080, #\u00a022. Leibniz-Zent. Inform., Wadern (2017)"},{"issue":"6","key":"239_CR17","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ipl.2005.02.013","volume":"94","author":"S Das","year":"2005","unstructured":"Das, S., Goswami, P.P., Nandy, S.C.: Smallest $$k$$-point enclosing rectangle and square of arbitrary orientation. Inf. Process. Lett. 94(6), 259\u2013266 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"239_CR18","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1006\/jagm.1995.1048","volume":"19","author":"A Datta","year":"1995","unstructured":"Datta, A., Lenhof, H.-P., Schwarz, Ch., Smid, M.: Static and dynamic algorithms for $$k$$-point clustering problems. J. Algorithms 19(3), 474\u2013503 (1995)","journal-title":"J. Algorithms"},{"issue":"3","key":"239_CR19","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02574012","volume":"11","author":"D Eppstein","year":"1994","unstructured":"Eppstein, D., Erickson, J.: Iterated nearest neighbors and finding minimal polytopes. Discrete Comput. Geom. 11(3), 321\u2013350 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"239_CR20","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"239_CR21","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00453-004-1123-0","volume":"41","author":"S Har-Peled","year":"2005","unstructured":"Har-Peled, S., Mazumdar, S.: Fast algorithms for computing the smallest $$k$$-enclosing circle. Algorithmica 41(3), 147\u2013157 (2005)","journal-title":"Algorithmica"},{"issue":"3","key":"239_CR22","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/s00454-010-9248-1","volume":"45","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S., Sharir, M.: Relative $$(p,\\epsilon )$$-approximations in geometry. Discrete Comput. Geom. 45(3), 462\u2013496 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"239_CR23","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A., Larsen, K.G.: Range selection and median: tight cell probe lower bounds and adaptive data structures. In: 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 805\u2013813. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.63"},{"key":"239_CR24","unstructured":"Kaplan, H., Roy, S., Sharir, M.: Finding axis-parallel rectangles of fixed perimeter of area containing the largest number of points. In: 25th European Symposium on Algorithms. Leibniz Int. Proc. Inform., vol.\u00a087, #\u00a052. Leibniz-Zent. Inform., Wadern (2017)"},{"issue":"3","key":"239_CR25","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. 2(3), 169\u2013186 (1992)","journal-title":"Comput. Geom."},{"key":"239_CR26","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: 42nd ACM International Symposium on Theory of Computing, pp. 603\u2013609. ACM, New York (2010)","DOI":"10.1145\/1806689.1806772"},{"issue":"2","key":"239_CR27","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0020-0190(97)00212-3","volume":"65","author":"M Segal","year":"1998","unstructured":"Segal, M., Kedem, K.: Enclosing $$k$$ points in the smallest axis parallel rectangle. Inf. Process. Lett. 65(2), 95\u201399 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"239_CR28","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. Assoc. Comput. Mach. 22(2), 215\u2013225 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"key":"239_CR29","doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: 46th ACM Symposium on Theory of Computing, pp. 664\u2013673. ACM, New York (2014)","DOI":"10.1145\/2591796.2591811"},{"issue":"2","key":"239_CR30","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.ipl.2015.09.002","volume":"116","author":"G Zhou","year":"2016","unstructured":"Zhou, G.: Two-dimensional range successor in optimal time and almost linear space. Inf. Process. Lett. 116(2), 171\u2013174 (2016)","journal-title":"Inf. Process. Lett."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00239-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00239-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00239-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T00:15:20Z","timestamp":1630541720000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00239-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,2]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["239"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00239-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,2]]},"assertion":[{"value":"16 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}