{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:50:19Z","timestamp":1769975419346,"version":"3.49.0"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2013,5,14]],"date-time":"2013-05-14T00:00:00Z","timestamp":1368489600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>We show that the expected number of maximal empty axis-parallel boxes amidst <jats:italic>n<\/jats:italic> random points in the unit hypercube [0,1]<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup> in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000187_inline2\"\/><jats:tex-math>$\\mathbb{R}^d$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is (1 \u00b1 <jats:italic>o<\/jats:italic>(1)) <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000187_inline1\"\/><jats:tex-math>$\\frac{(2d-2)!}{(d-1)!}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:italic>n<\/jats:italic> ln<jats:sup><jats:italic>d<\/jats:italic>\u22121<\/jats:sup><jats:italic>n<\/jats:italic>, if <jats:italic>d<\/jats:italic> is fixed. This estimate is relevant to analysis of the performance of exact algorithms for computing the largest empty axis-parallel box amidst <jats:italic>n<\/jats:italic> given points in an axis-parallel box <jats:italic>R<\/jats:italic>, especially the algorithms that proceed by examining all maximal empty boxes. Our method for bounding the expected number of maximal empty boxes also shows that the expected number of maximal empty orthants determined by <jats:italic>n<\/jats:italic> random points in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000187_inline2\"\/><jats:tex-math>$\\mathbb{R}^d$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is (1 \u00b1 <jats:italic>o<\/jats:italic>(1)) ln<jats:sup><jats:italic>d<\/jats:italic>\u22121<\/jats:sup><jats:italic>n<\/jats:italic>, if <jats:italic>d<\/jats:italic> is fixed. This estimate is related to the expected number of maximal (or minimal) points amidst random points, and has application to algorithms for coloured orthogonal range counting.<\/jats:p>","DOI":"10.1017\/s0963548313000187","type":"journal-article","created":{"date-parts":[[2013,5,14]],"date-time":"2013-05-14T12:51:11Z","timestamp":1368535871000},"page":"477-498","source":"Crossref","is-referenced-by-count":5,"title":["Maximal Empty Boxes Amidst Random Points"],"prefix":"10.1017","volume":"22","author":[{"given":"ADRIAN","family":"DUMITRESCU","sequence":"first","affiliation":[]},{"given":"MINGHUI","family":"JIANG","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2013,5,14]]},"reference":[{"key":"S0963548313000187_ref22","unstructured":"McKenna M. , O'Rourke J. and Suri S. (1985) Finding the largest rectangle in an orthogonal polygon. In Proc. 23rd Annual Allerton Conference on Communication, Control and Computing."},{"key":"S0963548313000187_ref20","unstructured":"Kurosh A. (1975) Higher Algebra, Mir."},{"key":"S0963548313000187_ref18","doi-asserted-by":"publisher","DOI":"10.1080\/00207168608803518"},{"key":"S0963548313000187_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/070684483"},{"key":"S0963548313000187_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00738-7"},{"key":"S0963548313000187_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9635-5"},{"key":"S0963548313000187_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(00)00047-5"},{"key":"S0963548313000187_ref19","volume-title":"Encyclopaedia of Mathematics","author":"Kudryavtsev","year":"2001"},{"key":"S0963548313000187_ref10","volume-title":"Principles and Techniques in Combinatorics","author":"Chuan-Chong","year":"1996"},{"key":"S0963548313000187_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/0215022"},{"key":"S0963548313000187_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322095"},{"key":"S0963548313000187_ref5","unstructured":"Backer J. and Keil M. (2009) The bichromatic rectangle problem in high dimensions. In Proc. 21st Canadian Conference on Computational Geometry, pp. 157\u2013160."},{"key":"S0963548313000187_ref4","unstructured":"Augustine J. , Das S. , Maheshwari A. , Nandy S. C. , Roy S. and Sarvattomananda S. (2010) Querying for the largest empty geometric object in a desired location. http:\/\/arxiv.org\/abs\/1004.0558v2"},{"key":"S0963548313000187_ref21","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"S0963548313000187_ref1","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1145\/41958.41988","article-title":"Fast algorithms for computing the largest empty rectangle","author":"Aggarwal","year":"1987","journal-title":"Proc. 3rd Annual Symposium on Computational Geometry"},{"key":"S0963548313000187_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90071-5"},{"key":"S0963548313000187_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90124-0"},{"key":"S0963548313000187_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553888"},{"key":"S0963548313000187_ref6","doi-asserted-by":"crossref","unstructured":"Backer J. and Keil M. (2010) The mono- and bichromatic empty rectangle and square problems in all dimensions. In Proc. 9th Latin American Symposium on Theoretical Informatics, pp. 14\u201325.","DOI":"10.1007\/978-3-642-12200-2_3"},{"key":"S0963548313000187_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009366"},{"key":"S0963548313000187_ref15","unstructured":"Giannopoulos P. , Knauer C. , Wahlstr\u00f6m M. and Werner D. (2011) Hardness of discrepancy computation and \u03f5-net verification in high dimension. J. Complexity, to appear."},{"key":"S0963548313000187_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(92)90115-O"},{"key":"S0963548313000187_ref16","doi-asserted-by":"crossref","unstructured":"Kaplan H. , Mozes S. , Nussbaum Y. and Sharir M. (2012) Submatrix maximum queries in Monge matrices and Monge partial matrices. and their applications. In Proc. 23rd ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 338\u2013355.","DOI":"10.1137\/1.9781611973099.31"},{"key":"S0963548313000187_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840377"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T21:15:15Z","timestamp":1556054115000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000187\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,14]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S0963548313000187"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000187","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,14]]}}}