{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T13:14:24Z","timestamp":1726146864384},"reference-count":30,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T00:00:00Z","timestamp":1650499200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2023,1]]},"abstract":"Abstract<\/jats:title>For integers and , a \u2010hole<\/jats:italic> in a set of points in general position in is a \u2010tuple of points from in convex position such that the interior of their convex hull does not contain any point from . For a convex body of unit \u2010dimensional volume, we study the expected number of \u2010holes in a set of points drawn uniformly and independently at random from . We prove an asymptotically tight lower bound on by showing that, for all fixed integers and , the number is at least . For some small holes, we even determine the leading constant exactly. We improve the currently best\u2010known lower bound on by Reitzner and Temesvari\u00a0(2019). In the plane, we show that the constant is independent of for every fixed and we compute it exactly for , improving earlier estimates by Fabila\u2010Monroy, Huemer, and Mitsche\u00a0and by the authors.<\/jats:p>","DOI":"10.1002\/rsa.21088","type":"journal-article","created":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T09:28:08Z","timestamp":1650533288000},"page":"29-51","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight bounds on the expected number of holes in random point sets"],"prefix":"10.1002","volume":"62","author":[{"given":"Martin","family":"Balko","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, Faculty of Mathematics and Physics Charles University Prague Czech Republic"}]},{"given":"Manfred","family":"Scheucher","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Mathematik Technische Universit\u00e4t Berlin Berlin Germany"}]},{"given":"Pavel","family":"Valtr","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Faculty of Mathematics and Physics Charles University Prague Czech Republic"}]}],"member":"311","published-online":{"date-parts":[[2022,4,21]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2020.105236"},{"key":"e_1_2_8_3_1","series-title":"Applied Mathematics Series","volume-title":"Handbook of mathematical functions: With formulas, graphs, and mathematical tables","author":"Abramowitz M.","year":"1965"},{"key":"e_1_2_8_4_1","unstructured":"B.Bukh T.Chao andR.Holzman On convex holes in D\u2010dimensional point sets.http:\/\/arXiv.org\/abs\/2007.08972 2020."},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1987-064-1"},{"key":"e_1_2_8_6_1","first-page":"436","article-title":"L\u00f6sung des 'Vierpunktproblems' von Sylvester aus der Theorie der geometrischen Wahrscheinlichkeiten","volume":"69","author":"Blaschke W.","year":"1917","journal-title":"Berichte \u00fcber die Verhandlungen der S\u00e4chsischen Akademie der Wissenschaften zu Leipzig. Mathematisch\u2010Physische Klasse"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-47392-0"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21037"},{"issue":"2","key":"e_1_2_8_9_1","first-page":"243","article-title":"Planar point sets with a small number of empty convex polygons","volume":"41","author":"B\u00e1r\u00e1ny I.","year":"2004","journal-title":"Studia Sci. Math. Hungarica"},{"key":"e_1_2_8_10_1","unstructured":"D.ConlonandJ.Lim Fixing a hole.http:\/\/arXiv.org\/abs\/2108.07087 2021."},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1201\/b18333"},{"key":"e_1_2_8_12_1","first-page":"52","article-title":"Some more problems on elementary geometry","volume":"5","author":"Erd\u0151s P.","year":"1978","journal-title":"Austr. Math. Soc. Gazette"},{"issue":"1","key":"e_1_2_8_13_1","first-page":"52","article-title":"Empty non\u2010convex and convex four\u2010gons in random point sets","volume":"52","author":"Fabila\u2010Monroy R.","year":"2015","journal-title":"Stud. Sci. Math. Hungarica"},{"key":"e_1_2_8_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9018-x"},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1973.45.525"},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1983-077-8"},{"key":"e_1_2_8_17_1","first-page":"187","volume-title":"Studies and essays, presented to R. Courant on his 60th birthday, January 8, 1948","author":"John F.","year":"1948"},{"key":"e_1_2_8_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1969.12000198"},{"key":"e_1_2_8_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01903339"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1951-008-7"},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"e_1_2_8_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00013-003-4808-8"},{"key":"e_1_2_8_23_1","doi-asserted-by":"crossref","unstructured":"D.MicciancioandP.Voulgaris Faster exponential time algorithms for the shortest vector problem Proc. 21st Annu. ACM\u2010SIAM Sympos. Discr. Algorithms SIAM Philadelphia PA 2010 pp. 1468\u20131480.","DOI":"10.1137\/1.9781611973075.119"},{"key":"e_1_2_8_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-1343-6"},{"key":"e_1_2_8_25_1","unstructured":"M.ReitznerandD.Temesvari Stars of empty simplices.http:\/\/arxiv.org\/abs\/1808.08734 2019."},{"key":"e_1_2_8_26_1","unstructured":"M.Scheucher Supplemental program for computer experiments.http:\/\/page.math.tu\u2010berlin.de\/scheuch\/suppl\/holes_in_random_sets\/ 2021."},{"key":"e_1_2_8_27_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2818.1988.tb04682.x"},{"key":"e_1_2_8_28_1","volume-title":"Encyclopedia of mathematics and its applications","author":"Schneider R.","year":"2014"},{"key":"e_1_2_8_29_1","volume-title":"Probability and its applications","author":"Schneider R.","year":"2008"},{"key":"e_1_2_8_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90665-3"},{"issue":"1","key":"e_1_2_8_31_1","first-page":"155","article-title":"On the minimum number of empty polygons in planar point sets","volume":"30","author":"Valtr P.","year":"1995","journal-title":"Studia Sci. Math. Hungarica"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21088","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.21088","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,22]],"date-time":"2023-08-22T11:09:58Z","timestamp":1692702598000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.21088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,21]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1002\/rsa.21088"],"URL":"https:\/\/doi.org\/10.1002\/rsa.21088","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,21]]},"assertion":[{"value":"2021-03-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}