{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:39:53Z","timestamp":1760402393577,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,1,5]],"date-time":"2022-01-05T00:00:00Z","timestamp":1641340800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002527","name":"Kyonggi University","doi-asserted-by":"publisher","award":["Research Grant 2021"],"award-info":[{"award-number":["Research Grant 2021"]}],"id":[{"id":"10.13039\/501100002527","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Let S be a set of n points in the general position, that is, no three points in S are collinear. A simple k-gon with all corners in S such that its interior avoids any point of S is called a k-hole. In this paper, we present the first algorithm that counts the number of non-convex 5-holes in S. To our best knowledge, prior to this work there was no known algorithm in the literature except a trivial brute force algorithm. Our algorithm runs in time O(T+Q), where T denotes the number of 3-holes, or empty triangles, in S and Q that denotes the number of non-convex 4-holes in S. Note that T+Q ranges from \u03a9(n2) to O(n3), while its expected number is \u0398(n2logn) when the points in S are chosen uniformly and independently at random from a convex and bounded body in the plane.<\/jats:p>","DOI":"10.3390\/sym14010078","type":"journal-article","created":{"date-parts":[[2022,1,9]],"date-time":"2022-01-09T23:35:09Z","timestamp":1641771309000},"page":"78","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Counting Non-Convex 5-Holes in a Planar Point Set"],"prefix":"10.3390","volume":"14","author":[{"given":"Young-Hun","family":"Sung","sequence":"first","affiliation":[{"name":"Division of AI Computer Science and Engineering, Kyonggi University, Suwon 16227, Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8802-4247","authenticated-orcid":false,"given":"Sang Won","family":"Bae","sequence":"additional","affiliation":[{"name":"Division of AI Computer Science and Engineering, Kyonggi University, Suwon 16227, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/BF01840404","article-title":"Searching for empty convex polygons","volume":"5","author":"Dobkin","year":"1990","journal-title":"Algorithmica"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0020-0190(91)90237-C","article-title":"Counting k-subsets and convex k-gons in the plane","volume":"38","author":"Rote","year":"1991","journal-title":"Inform. Proc. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0190(95)00130-5","article-title":"Counting convex polygons in planar point sets","volume":"56","author":"Mitchell","year":"1995","journal-title":"Inform. Proc. Lett."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0020-0190(92)90178-X","article-title":"Counting convex k-gons in planar point sets","volume":"41","author":"Rote","year":"1992","journal-title":"Inform. Proc. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"106221","DOI":"10.1016\/j.ipl.2021.106221","article-title":"Faster counting empty convex polygons in a planar point set","volume":"175","author":"Bae","year":"2022","journal-title":"Inform. Proc. Lett."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"436","DOI":"10.4153\/CMB-1987-064-1","article-title":"Empty simplices in Euclidean space","volume":"30","year":"1987","journal-title":"Canad. Math. Bull."},{"key":"ref_7","first-page":"14:1","article-title":"Holes and Islands in Random Point Sets","volume":"Volume 164","author":"Cabello","year":"2020","journal-title":"Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020)"},{"key":"ref_8","first-page":"1094","article-title":"Counting Convex and Non-convex 4-Holes in a Point Set","volume":"E104.A","author":"Sung","year":"2021","journal-title":"Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1016\/j.comgeo.2013.12.004","article-title":"4-Holes in point sets","volume":"47","author":"Aichholzer","year":"2014","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_10","first-page":"52","article-title":"Empty Non-convex and Convex Four-gons in Random Point Sets","volume":"52","author":"Huemer","year":"2015","journal-title":"Stud. Sci. Math. Hung."},{"key":"ref_11","first-page":"243","article-title":"Planar point sets with a small number of empty convex polygons","volume":"41","author":"Valtr","year":"2005","journal-title":"Stud. Sci. Math. Hung."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1016\/j.comgeo.2014.12.007","article-title":"On k-gons and k-holes in point sets","volume":"48","author":"Aichholzer","year":"2015","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"482","DOI":"10.4153\/CMB-1983-077-8","article-title":"Sets with no empty convex 7-gons","volume":"26","author":"Horton","year":"1983","journal-title":"Canad. Math. Bull."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"105236","DOI":"10.1016\/j.jcta.2020.105236","article-title":"A superlinear lower bound on the number of 5-holes","volume":"173","author":"Aichholzer","year":"2020","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_15","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Szekeres","year":"1935","journal-title":"Compos. Math."},{"key":"ref_16","first-page":"53","article-title":"On some extremum problems in elementary geometry","volume":"3\u20134","author":"Szekeres","year":"1961","journal-title":"Ann. Univ. Sci. Bp. E\u00f6tv\u00f6s Sect. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1017\/S144618110000300X","article-title":"Computer solution to the 17-point Erd\u0151s\u2013Szekeres problem","volume":"48","author":"Szekeres","year":"2006","journal-title":"ANZIAM J."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.1090\/jams\/869","article-title":"On the Erd\u0151s\u2013Szekeres Convex Polygon Problem","volume":"30","author":"Suk","year":"2021","journal-title":"J. Am. Math. Soc."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"3981","DOI":"10.4171\/jems\/1000","article-title":"Two extensions of the Erd\u0151s\u2013Szekeres Problem","volume":"22","author":"Holmsen","year":"2021","journal-title":"J. Eur. Math. Soc."},{"key":"ref_20","first-page":"52","article-title":"Some more problems on elementary geometry","volume":"5","year":"1978","journal-title":"Austral. Math. Soc. Gaz."},{"key":"ref_21","first-page":"116","article-title":"Kovexe F\u00fcnfecke in ebenen Punktmengen","volume":"33","author":"Harborth","year":"1978","journal-title":"Elem. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/s00454-007-1343-6","article-title":"The Empty Hexagon Theorem","volume":"38","year":"2007","journal-title":"Discret. Comput. Geom."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s00454-007-9018-x","article-title":"Empty Convex Hexagons in Planar Point Sets","volume":"39","author":"Gerken","year":"2008","journal-title":"Discret. Comput. Geom."},{"key":"ref_24","unstructured":"Nash, J.F., and Rassias, M.T. (2016). The Erd\u0151s\u2013Szekeres Problem. Open Problems in Mathematics, Springer International Publishing."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1090\/S0273-0979-00-00877-6","article-title":"The Erd\u0151s\u2013Szekeres problem on points in convex position\u2014A survey","volume":"33","author":"Morris","year":"2000","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_26","first-page":"155","article-title":"On the minimum number of empty polygons in planar point sets","volume":"30","author":"Valtr","year":"1995","journal-title":"Stud. Sci. Math. Hung."},{"key":"ref_27","first-page":"93","article-title":"Planar Sets with Few Empty Convex Polygons","volume":"36","author":"Dumistrescu","year":"2000","journal-title":"Stud. Sci. Math. Hung."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.jcta.2005.03.007","article-title":"On empty convex polygons in a planar point set","volume":"113","author":"Pinchasi","year":"2006","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1137\/0605009","article-title":"On the Size of Separating Systems and Families of Perfect Hash Functions","volume":"5","author":"Fredman","year":"1984","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_30","first-page":"682","article-title":"Hash, Displace, and Compress","volume":"Volume 5757","author":"Fiat","year":"2009","journal-title":"European Symposium on Algorithms"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/1\/78\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:36:22Z","timestamp":1760362582000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/1\/78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,5]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["sym14010078"],"URL":"https:\/\/doi.org\/10.3390\/sym14010078","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2022,1,5]]}}}