{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:38:12Z","timestamp":1772908692148,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,2,23]],"date-time":"2017-02-23T00:00:00Z","timestamp":1487808000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00454-017-9871-1","type":"journal-article","created":{"date-parts":[[2017,2,23]],"date-time":"2017-02-23T15:34:47Z","timestamp":1487864087000},"page":"742-756","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Number of Maximum Empty Boxes Amidst n Points"],"prefix":"10.1007","volume":"59","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]},{"given":"Minghui","family":"Jiang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,23]]},"reference":[{"issue":"2","key":"9871_CR1","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0097-3165(89)90032-0","volume":"52","author":"PK Agarwal","year":"1989","unstructured":"Agarwal, P.K., Sharir, M., Shor, P.: Sharp upper and lower bounds on the length of general Davenport\u2013Schinzel sequences. J. Comb. Theory Ser. A 52(2), 228\u2013274 (1989)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"1\u20132","key":"9871_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0166-218X(90)90124-U","volume":"27","author":"A Aggarwal","year":"1990","unstructured":"Aggarwal, A., Klawe, M.: Applications of generalized matrix searching to geometric algorithms. Discrete Appl. Math. 27(1\u20132), 3\u201323 (1990)","journal-title":"Discrete Appl. Math."},{"key":"9871_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Suri, S.: Fast algorithms for computing the largest empty rectangle. In: 3rd Annual Symposium on Computational Geometry (SCG\u201987), pp.\u00a0278\u2013290. ACM, New York (1987)","DOI":"10.1145\/41958.41988"},{"issue":"2","key":"9871_CR4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M.M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2(2), 195\u2013208 (1987)","journal-title":"Algorithmica"},{"key":"9871_CR5","unstructured":"Aistleitner, C., Hinrichs, A., Rudolf, D.: On the size of the largest empty box amidst a point set (2015). \n                        arXiv:1507.02067"},{"issue":"1","key":"9871_CR6","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(86)90071-5","volume":"13","author":"MJ Atallah","year":"1986","unstructured":"Atallah, M.J., Frederickson, G.N.: A note on finding a maximum empty rectangle. Discrete Appl. Math. 13(1), 87\u201391 (1986)","journal-title":"Discrete Appl. Math."},{"key":"9871_CR7","unstructured":"Augustine, J., Das, S., Maheshwari, A., Nandy, S., Roy, S., Sarvattomananda, S.: Querying for the largest empty geometric object in a desired location (2010). \n                        arXiv:1004.0558"},{"key":"9871_CR8","unstructured":"Backer, J., Keil, J.M.: The bichromatic rectangle problem in high dimensions. In: Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pp.\u00a0157\u2013160. Vancouver (2009)"},{"key":"9871_CR9","doi-asserted-by":"crossref","unstructured":"Backer, J., Keil, J.M.: The mono- and bichromatic empty rectangle and square problems in all dimensions. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010: Theoretical Informatics, pp.\u00a014\u201325. Lecture Notes in Computer Science, vol. 6034. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-12200-2_3"},{"key":"9871_CR10","unstructured":"Boland, R.P., Urrutia, J.: Finding the largest axis aligned rectangle in a polygon in \n                        $$O(n \\log {n})$$\n                        \n                            \n                                \n                                    O\n                                    (\n                                    n\n                                    log\n                                    n\n                                    )\n                                \n                            \n                        \n                     time. In: Proceedings of the 13st Canadian Conference on Computational Geometry (CCCG2001), pp.\u00a041\u201344. Vancouver (2001)"},{"issue":"1","key":"9871_CR11","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s00454-001-0010-6","volume":"26","author":"P Bra\u00df","year":"2001","unstructured":"Bra\u00df, P., Rote, G., Swanepoel, K.J.: Triangles of extremal area or perimeter in a finite planar point set. Discrete Comput. Geom. 26(1), 51\u201358 (2001)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9871_CR12","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0215022","volume":"15","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., Drysdale, R.L., Lee, D.T.: Computing the largest empty rectangle. SIAM J. Comput. 15(1), 300\u2013315 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9871_CR13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0020-0255(00)00047-5","volume":"128","author":"A Datta","year":"2000","unstructured":"Datta, A., Soundaralakshmi, S.: An efficient algorithm for computing the maximum empty rectangle in three dimensions. Inform. Sci. 128(1\u20132), 43\u201365 (2000)","journal-title":"Inform. Sci."},{"issue":"3","key":"9871_CR14","doi-asserted-by":"crossref","first-page":"684","DOI":"10.2307\/2373068","volume":"87","author":"H Davenport","year":"1965","unstructured":"Davenport, H., Schinzel, A.: A combinatorial problem connected with differential equations. Am. J. Math. 87(3), 684\u2013694 (1965)","journal-title":"Am. J. Math."},{"issue":"2","key":"9871_CR15","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1145\/103516.103518","volume":"38","author":"D Dobkin","year":"1991","unstructured":"Dobkin, D., Suri, S.: Maintenance of geometric extrema. J. Assoc. Comput. Mach. 38(2), 275\u2013298 (1991)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"9871_CR16","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s00453-012-9635-5","volume":"66","author":"A Dumitrescu","year":"2013","unstructured":"Dumitrescu, A., Jiang, M.: On the largest empty axis-parallel box amidst \n                        $$n$$\n                        \n                            \n                                n\n                            \n                        \n                     points. Algorithmica 66(2), 225\u2013248 (2013)","journal-title":"Algorithmica"},{"issue":"4","key":"9871_CR17","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1017\/S0963548313000187","volume":"22","author":"A Dumitrescu","year":"2013","unstructured":"Dumitrescu, A., Jiang, M.: Maximal empty boxes amidst random points. Comb. Probab. Comput. 22(4), 477\u2013498 (2013)","journal-title":"Comb. Probab. Comput."},{"issue":"4","key":"9871_CR18","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1145\/2696081.2696096","volume":"45","author":"A Dumitrescu","year":"2014","unstructured":"Dumitrescu, A., Jiang, M.: Computational geometry column 60. ACM SIGACT News 45(4), 76\u201382 (2014)","journal-title":"ACM SIGACT News"},{"key":"9871_CR19","unstructured":"Dumitrescu, A., Jiang, M.: Perfect vector sets, properly overlapping partitions, and largest empty box (2016). \n                        arXiv:1608.06874"},{"issue":"3","key":"9871_CR20","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/S0304-3975(02)00738-7","volume":"296","author":"J Edmonds","year":"2003","unstructured":"Edmonds, J., Gryz, J., Liang, D., Miller, R.J.: Mining for empty spaces in large data sets. Theor. Comput. Sci. 296(3), 435\u2013452 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9871_CR21","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/0097-3165(71)90028-8","volume":"10","author":"P Erd\u0151s","year":"1971","unstructured":"Erd\u0151s, P., Purdy, G.: Some extremal problems in geometry. J. Comb. Theory Ser. A 10, 246\u2013252 (1971)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"2","key":"9871_CR22","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/j.jco.2011.09.001","volume":"28","author":"P Giannopoulos","year":"2012","unstructured":"Giannopoulos, P., Knauer, C., Wahlstr\u00f6m, M., Werner, D.: Hardness of discrepancy computation and \n                        $$\\varepsilon $$\n                        \n                            \n                                \u03b5\n                            \n                        \n                    -net verification in high dimension. J. Complexity 28(2), 162\u2013176 (2012)","journal-title":"J. Complexity"},{"key":"9871_CR23","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/BF01386213","volume":"2","author":"JH Halton","year":"1960","unstructured":"Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84\u201390 (1960)","journal-title":"Numer. Math."},{"key":"9871_CR24","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1111\/j.1749-6632.1960.tb42846.x","volume":"86","author":"JM Hammersley","year":"1960","unstructured":"Hammersley, J.M.: Monte Carlo methods for solving multivariable problems. Ann. New York Acad. Sci. 86, 844\u2013874 (1960)","journal-title":"Ann. New York Acad. Sci."},{"issue":"2","key":"9871_CR25","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S Hart","year":"1986","unstructured":"Hart, S., Sharir, M.: Nonlinearity of Davenport\u2013Schinzel sequences and of generalized path compression schemes. Combinatorica 6(2), 151\u2013177 (1986)","journal-title":"Combinatorica"},{"issue":"3","key":"9871_CR26","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1137\/070684483","volume":"38","author":"H Kaplan","year":"2008","unstructured":"Kaplan, H., Rubin, N., Sharir, M., Verbin, E.: Efficient colored orthogonal range counting. SIAM J. Comput. 38(3), 982\u20131011 (2008)","journal-title":"SIAM J. Comput."},{"key":"9871_CR27","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Mozes, S., Nussbaum, Y., Sharir, M.: Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0338\u2013355. ACM, New York (2012)","DOI":"10.1137\/1.9781611973099.31"},{"key":"9871_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-03942-3","volume-title":"Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics","author":"J Matou\u0161ek","year":"1999","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics, vol. 18. Springer, Berlin (1999)"},{"key":"9871_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, Berlin (2002)"},{"issue":"3","key":"9871_CR30","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0166-218X(84)90124-0","volume":"8","author":"A Naamad","year":"1984","unstructured":"Naamad, A., Lee, D.T., Hsu, W.-L.: On the maximum empty rectangle problem. Discrete Appl. Math. 8(3), 267\u2013277 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9871_CR31","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0898-1221(98)00125-4","volume":"36","author":"SC Nandy","year":"1998","unstructured":"Nandy, S.C., Bhattacharya, B.B.: Maximal empty cuboids among points and blocks. Comput. Math. Appl. 36(3), 11\u201320 (1998)","journal-title":"Comput. Math. Appl."},{"key":"9871_CR32","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction. Texts and Monographs in Computer Science","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, New York (1985)"},{"issue":"8\u20139","key":"9871_CR33","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0895-7177(96)00036-2","volume":"23","author":"G Rote","year":"1996","unstructured":"Rote, G., Tichy, R.F.: Quasi-Monte-Carlo methods and the dispersion of point sequences. Math. Comput. Modelling 23(8\u20139), 9\u201323 (1996)","journal-title":"Math. Comput. Modelling"},{"key":"9871_CR34","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"key":"9871_CR35","first-page":"813","volume":"38","author":"JG Corput van der","year":"1935","unstructured":"van der Corput, J.G.: Verteilungsfunktionen. I. Proc. Nederl. Akad. Wetensch. 38, 813\u2013821 (1935)","journal-title":"Proc. Nederl. Akad. Wetensch."},{"key":"9871_CR36","first-page":"1058","volume":"38","author":"JG Corput van der","year":"1935","unstructured":"van der Corput, J.G.: Verteilungsfunktionen. II. Proc. Nederl. Akad. Wetensch. 38, 1058\u20131066 (1935)","journal-title":"Proc. Nederl. Akad. Wetensch."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9871-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9871-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9871-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T15:56:05Z","timestamp":1519919765000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9871-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,23]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9871"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9871-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,23]]}}}