{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:36Z","timestamp":1750220856120,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2019,9,24]]},"abstract":"<jats:p>We revisit the following problem called Maximum Empty Box: Given a set S of n points inside an axis-parallel box U in Rd, nd a maximum-volume axis-parallel box that is contained in U but contains no points of S in its interior.<\/jats:p>","DOI":"10.1145\/3364626.3364638","type":"journal-article","created":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T12:57:52Z","timestamp":1569416272000},"page":"75-90","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Computational Geometry Column 69"],"prefix":"10.1145","volume":"50","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"University of Wisconsin-Milwaukee, Milwaukee, WI, USA"}]},{"given":"Minghui","family":"Jiang","sequence":"additional","affiliation":[{"name":"Utah State University, Logan, UT, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,9,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90124-U"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/41958.41988"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.06.008"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90071-5"},{"key":"e_1_2_1_7_1","first-page":"160","volume-title":"Proceedings of the 21st Canadian Conference on Computational Geometry","author":"Backer J.","year":"2009"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2002.3295"},{"key":"e_1_2_1_10_1","first-page":"452","article-title":"On generalized graphs","volume":"16","author":"B.","year":"1965","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"e_1_2_1_11_1","first-page":"366","article-title":"Sperner systems consisting of pairs of complementary subsets, Journal of Com- binatorial Theory","volume":"15","author":"B.","year":"1973","journal-title":"Series A"},{"volume-title":"Hypergraphs, Families of Vectors, and Combinatorial Probability","year":"1986","author":"B.","key":"e_1_2_1_12_1"},{"volume-title":"Combinatorics (Proc. Conf. Combinatorial Math.","year":"1972","author":"Brace B. A.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215022"},{"key":"e_1_2_1_15_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"e_1_2_1_16_1","first-page":"821","volume":"38","author":"J. G. van der Corp","year":"1935","journal-title":"Proc. Nederl. Akad. Wetensch."},{"key":"e_1_2_1_17_1","first-page":"1066","volume":"38","author":"J. G. van der Corp","year":"1935","journal-title":"Proc. Nederl. Akad. Wetensch."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(00)00047-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9635-5"},{"key":"e_1_2_1_20_1","first-page":"498","article-title":"Maximal empty boxes amidst random points, Combinatorics","volume":"22","author":"Dumitrescu A.","year":"2013","journal-title":"Probability and Computing"},{"issue":"4","key":"e_1_2_1_21_1","first-page":"82","article-title":"Computational Geometry Column 60","volume":"45","author":"Dumitrescu A.","year":"2014","journal-title":"SIGACT News Bulletin"},{"volume-title":"Perfect vector sets, properly overlapping partitions, and largest empty box, preprint","year":"2016","author":"Dumitrescu A.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9871-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00738-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90016-N"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01195325"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2011.09.001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386213"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1111\/j.1749-6632.1960.tb42846.x","article-title":"Carlo methods for solving multivariable problems","volume":"86","author":"Hammersley J. M.","year":"1960","journal-title":"Ann. New York Acad. Sci."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.31"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/070684483"},{"key":"e_1_2_1_32_1","first-page":"26","article-title":"search theory and truth functions) of Sperner type theorems","author":"Katona G. O. H.","year":"1973","journal-title":"Periodica Mathematica Hungarica 3(1--2) ("},{"volume-title":"Studia Scientiarum Mathe- maticarum Hungarica 26","year":"1991","author":"Katona G. O. H.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90098-8"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90100-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.11.005"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511987045"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80035-2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03942-3"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1108023"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90124-0"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90081-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(96)00036-2"},{"volume-title":"An upper bound of the minimal dispersion via delta covers, preprint","year":"2017","author":"Rudolf D.","key":"e_1_2_1_44_1"},{"volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","year":"1995","author":"Sharir M.","key":"e_1_2_1_45_1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.11.006"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01171114"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.matcom.2015.12.005"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.11.003"},{"volume-title":"Deterministic constructions of high-dimensional sets with small dispersion, preprint","year":"2019","author":"Ullrich M.","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/00630343"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364626.3364638","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3364626.3364638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:24Z","timestamp":1750202604000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364626.3364638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,24]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,24]]}},"alternative-id":["10.1145\/3364626.3364638"],"URL":"https:\/\/doi.org\/10.1145\/3364626.3364638","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2019,9,24]]},"assertion":[{"value":"2019-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}