{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,3]],"date-time":"2023-09-03T12:43:59Z","timestamp":1693745039073},"reference-count":26,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2023,9,1]]},"DOI":"10.1587\/transfun.2022dmp0007","type":"journal-article","created":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T22:11:53Z","timestamp":1680473513000},"page":"1082-1091","source":"Crossref","is-referenced-by-count":0,"title":["Enumerating Empty and Surrounding Polygons"],"prefix":"10.1587","volume":"E106.A","author":[{"given":"Shunta","family":"TERUI","sequence":"first","affiliation":[{"name":"Iwate University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsuhisa","family":"YAMANAKA","sequence":"additional","affiliation":[{"name":"Iwate University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"HIRAYAMA","sequence":"additional","affiliation":[{"name":"Iwate University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"HORIYAMA","sequence":"additional","affiliation":[{"name":"Hokkaido University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhiro","family":"KURITA","sequence":"additional","affiliation":[{"name":"Nagoya University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeaki","family":"UNO","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] K. Wasa, \u201cEnumeration of enumeration algorithms,\u201d CoRR, vol.abs\/1605.05102, 2016. 10.48550\/arXiv.1605.05102"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] D. Avis and K. Fukuda, \u201cReverse search for enumeration,\u201d Discrete Applied Mathematics, vol.65, no.1-3, pp.21-46, 1996. 10.1016\/0166-218x(95)00026-n","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] S. Bespamyatnikh, \u201cAn efficient algorithm for enumeration of triangulations,\u201d Computational Geometry, vol.23, no.3, pp.271-279, 2002. 10.1016\/s0925-7721(02)00111-6","DOI":"10.1016\/S0925-7721(02)00111-6"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] N. Katoh and S. Tanigawa, \u201cEnumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees,\u201d Discrete Applied Mathematics, vol.157, no.17, pp.3569-3585, 2009. 10.1016\/j.dam.2009.04.019","DOI":"10.1016\/j.dam.2009.04.019"},{"key":"5","unstructured":"[5] M. Wettstein, \u201cCounting and enumerating crossing-free geometric graphs,\u201d Journal of Computational Geometry, vol.8, no.1, pp.47-77, 2017. 10.20382\/jocg.v8i1a4"},{"key":"6","unstructured":"[6] Y. Nakahata, T. Horiyama, S. Minato, and K. Yamanaka, \u201cCompiling crossing-free geometric graphs with connectivity constraint for fast enumeration, random sampling, and optimization,\u201d CoRR, vol.abs\/2001.08899, 2020. 10.48550\/arXiv.2001.08899"},{"key":"7","unstructured":"[7] K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara, and K. Nakada, \u201cEfficient enumeration of pseudoline arrangements,\u201d Proc. European Workshop on Computational Geometry 2009, pp.143-146, March 2009."},{"key":"8","unstructured":"[8] T. Horiyama and W. Shoji, \u201cEdge unfoldings of platonic solids never overlap,\u201d Proc. 23rd Annual Canadian Conference on Computational Geometry, pp.65-70, 2011."},{"key":"9","unstructured":"[9] T. Horiyama, M. Miyasaka, and R. Sasaki, \u201cIsomorphism elimination by zero-suppressed binary decision diagrams,\u201d Proc. 30th Canadian Conference on Computational Geometry, CCCG 2018, Aug. 2018, University of Manitoba, Winnipeg, Manitoba, Canada, S. Durocher and S. Kamali, eds., pp.360-366, 2018."},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] G. Rote, G.J. Woeginger, B. Zhu, and Z. Wang, \u201cCounting k-subsets and convex k-gons in the plane,\u201d Inf. Process. Lett., vol.38, no.3, pp.149-151, 1991. 10.1016\/0020-0190(91)90237-c","DOI":"10.1016\/0020-0190(91)90237-C"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] G. Rote and G.J. Woeginger, \u201cCounting convex k-gons in planar point sets,\u201d Inf. Process. Lett., vol.41, no.4, pp.191-194, 1992. 10.1016\/0020-0190(92)90178-x","DOI":"10.1016\/0020-0190(92)90178-X"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] J.S.B. Mitchell, G. Rote, G. Sundaram, and G.J. Woeginger, \u201cCounting convex polygons in planar point sets,\u201d Inf. Process. Lett., vol.56, no.1, pp.45-49, 1995. 10.1016\/0020-0190(95)00130-5","DOI":"10.1016\/0020-0190(95)00130-5"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] D.P. Dobkin, H. Edelsbrunner, and M.H. Overmars, \u201cSearching for empty convex polygons,\u201d Algorithmica, vol.5, no.4, pp.561-571, 1990. 10.1007\/bf01840404","DOI":"10.1007\/BF01840404"},{"key":"14","unstructured":"[14] D. Marx and T. Miltzow, \u201cPeeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems,\u201d 32nd International Symposium on Computational Geometry, SoCG 2016, June 2016, Boston, MA, USA, pp.52:1-52:16, 2016."},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] T. Auer and M. Held, \u201cHeuristics for the generation of random polygons,\u201d Proc. 8th Canadian Conference on Computational Geometry, pp.38-43, 1996.","DOI":"10.1515\/9780773591134-009"},{"key":"16","unstructured":"[16] C. Sohler, \u201cGenerating random star-shaped polygons,\u201d Proc. 11th Canadian Conference on Computational Geometry, pp.174-177, 1999."},{"key":"17","unstructured":"[17] S. Teramoto, M. Motoki, R. Uehara, and T. Asano, \u201cHeuristics for generating a simple polygonalization,\u201d IPSJ SIG Technical Report, 2006-AL-106(6), Information Processing Society of Japan, May 2006."},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] C. Zhu, G. Sundaram, J. Snoeyink, and J.S.B. Mitchell, \u201cGenerating random polygons with given vertices,\u201d Computational Geometry, vol.6, no.5, pp.277-290, 1996. 10.1016\/0925-7721(95)00031-3","DOI":"10.1016\/0925-7721(95)00031-3"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] K. Yamanaka, D. Avis, T. Horiyama, Y. Okamoto, R. Uehara, and T. Yamauchi, \u201cAlgorithmic enumeration of surrounding polygons,\u201d Discrete Applied Mathematics, vol.303, pp.305-313, 2021. 10.1016\/j.dam.2020.03.034","DOI":"10.1016\/j.dam.2020.03.034"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] K. Yamanaka and S. Nakano, \u201cListing all plane graphs,\u201d Proc. Second International Workshop on Algorithms and Computation, (WALCOM 2008), LNCS, vol.4921, pp.210-221, 2008. 10.1007\/978-3-540-77891-2_20","DOI":"10.1007\/978-3-540-77891-2_20"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] G.H. Meisters, \u201cPolygons have ears,\u201d American Mathematical Monthly, vol.82, no.6, pp.648-651, 1975. 10.1080\/00029890.1975.11993898","DOI":"10.1080\/00029890.1975.11993898"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] D. Avis, \u201cGenerating rooted triangulations without repetitions,\u201d Algorithmica, vol.16, pp.618-632, 1996. 10.1007\/bf01944353","DOI":"10.1007\/BF01944353"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] P.P. Goswami, S. Das, and S.C. Nandy, \u201cTriangular range counting query in 2D and its application in finding <i>k<\/i> nearest neighbors of a line segment,\u201d Computational Geometry, vol.29, no.3, pp.163-175, 2004. 10.1016\/j.comgeo.2004.02.001","DOI":"10.1016\/j.comgeo.2004.02.001"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] B. Chazelle, H. Edelsbrunner, M. Grigni, L.J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink, \u201cRay shooting in polygons using geodesic triangulations,\u201d Algorithmica, vol.12, no.1, pp.54-68, 1994. 10.1007\/bf01377183","DOI":"10.1007\/BF01377183"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] B. Chazelle and L.J. Guibas, \u201cVisibility and intersection problems in plane geometry,\u201d Discrete Comput. Geom., vol.4, pp.551-581, 1989. 10.1007\/bf02187747","DOI":"10.1007\/BF02187747"},{"key":"26","doi-asserted-by":"publisher","unstructured":"[26] S. Nakano and T. Uno, \u201cGenerating colored trees,\u201d Proc. 31th Workshop on Graph-Theoretic Concepts in Computer Science, (WG 2005), LNCS, vol.3787, pp.249-260, 2005. 10.1007\/11604686_22","DOI":"10.1007\/11604686_22"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/9\/E106.A_2022DMP0007\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T03:27:14Z","timestamp":1693625234000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/9\/E106.A_2022DMP0007\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,1]]},"references-count":26,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2022dmp0007","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,1]]},"article-number":"2022DMP0007"}}