{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T08:11:29Z","timestamp":1648973489251},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2017,5,30]],"date-time":"2017-05-30T00:00:00Z","timestamp":1496102400000},"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":[[2017,9]]},"abstract":"<jats:p>We show that the maximum number of convex polygons in a triangulation of<jats:italic>n<\/jats:italic>points in the plane is<jats:italic>O<\/jats:italic>(1.5029<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>). This improves an earlier bound of<jats:italic>O<\/jats:italic>(1.6181<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>) established by van Kreveld, L\u00f6ffler and Pach (2012), and almost matches the current best lower bound of \u03a9(1.5028<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>) due to the same authors. Given a planar straight-line graph<jats:italic>G<\/jats:italic>with<jats:italic>n<\/jats:italic>vertices, we also show how to compute efficiently the number of convex polygons in<jats:italic>G<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548317000141","type":"journal-article","created":{"date-parts":[[2017,5,30]],"date-time":"2017-05-30T06:12:52Z","timestamp":1496124772000},"page":"641-659","source":"Crossref","is-referenced-by-count":3,"title":["Convex Polygons in Geometric Triangulations"],"prefix":"10.1017","volume":"26","author":[{"given":"ADRIAN","family":"DUMITRESCU","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CSABA D.","family":"T\u00d3TH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,5,30]]},"reference":[{"key":"S0963548317000141_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0704-5"},{"key":"S0963548317000141_ref29","unstructured":"Wettstein M. (2016) Counting and enumerating crossing-free geometric graphs. In Proc. 30th Symposium on Computational Geometry (SOCG), ACM Press, pp. 1\u201310. Full paper available at arXiv:1604.05350."},{"key":"S0963548317000141_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.039"},{"key":"S0963548317000141_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/050636036"},{"key":"S0963548317000141_ref16","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s","year":"1935","journal-title":"Compositio Math."},{"key":"S0963548317000141_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00183192"},{"key":"S0963548317000141_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2421119.2421136"},{"key":"S0963548317000141_ref8","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009"},{"key":"S0963548317000141_ref28","unstructured":"Sheffer A. (2015) Numbers of plane graphs. https:\/\/adamsheffer.wordpress.com\/numbers-of-plane-graphs\/"},{"key":"S0963548317000141_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/110849407"},{"key":"S0963548317000141_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-015-1621-7"},{"key":"S0963548317000141_ref19","doi-asserted-by":"crossref","unstructured":"van Kreveld M. J. , L\u00f6ffler M. and Pach J. (2012) How many potatoes are in a mesh? In Proc. 23rd International Symposium on Algebraic Computation (ISAAC), Vol. 7676 of Lecture Notes in Computer Science, Springer, pp. 166\u2013176.","DOI":"10.1007\/978-3-642-35261-4_20"},{"key":"S0963548317000141_ref13","doi-asserted-by":"crossref","unstructured":"Dumitrescu A. and T\u00f3th C. D. (2017) Convex polygons in geometric triangulations. arXiv:1411.1303v3","DOI":"10.1017\/S0963548317000141"},{"key":"S0963548317000141_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.01.002"},{"key":"S0963548317000141_ref20","unstructured":"Marx D. and Miltzow T. (2016) Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems. In Proc. 32nd International Symposium on Computational Geometry (SoCG), LIPIcs 51, Schloss Dagstuhl, article 52."},{"key":"S0963548317000141_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.12.006"},{"key":"S0963548317000141_ref24","doi-asserted-by":"crossref","first-page":"P70","DOI":"10.37236\/557","article-title":"Counting triangulations of planar point sets","volume":"18","author":"Sharir","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S0963548317000141_ref4","doi-asserted-by":"crossref","unstructured":"Alvarez V. and Seidel R. (2013) A simple aggregative algorithm for counting triangulations of planar point sets and related problems. In Proc. 29th Symposium on Computational Geometry (SoCG), ACM Press, pp. 1\u20138.","DOI":"10.1145\/2462356.2462392"},{"key":"S0963548317000141_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187823"},{"key":"S0963548317000141_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9346-8"},{"key":"S0963548317000141_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831300031X"},{"key":"S0963548317000141_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187692"},{"key":"S0963548317000141_ref21","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-00-00877-6"},{"key":"S0963548317000141_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19391-0_3"},{"key":"S0963548317000141_ref6","doi-asserted-by":"crossref","unstructured":"Buchin K. , Knauer C. , Kriegel K. , Schulz A. and Seidel R. (2007) On the number of cycles in planar graphs. In Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON), Vol. 4598 of Lecture Notes in Computer Science, Springer, pp. 97\u2013107.","DOI":"10.1007\/978-3-540-73545-8_12"},{"key":"S0963548317000141_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00010-9"},{"key":"S0963548317000141_ref10","doi-asserted-by":"crossref","unstructured":"Dumitrescu A. , Mandal R. and T\u00f3th C. D. (2016) Monotone paths in geometric triangulations. arXiv:1608.04812. Extended abstract of an earlier version in Proc. 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), Vol. 9843 of Lecture Notes in Computer Science, Springer, pp. 411\u2013422.","DOI":"10.1007\/978-3-319-44543-4_32"},{"key":"S0963548317000141_ref15","first-page":"52","article-title":"Some more problems on elementary geometry","volume":"5","author":"Erd\u0151s","year":"1978","journal-title":"Gazette Austral. Math. Soc."},{"key":"S0963548317000141_ref2","first-page":"9","article-title":"Crossing-free subgraphs","volume":"12","author":"Ajtai","year":"1982","journal-title":"Ann. Discrete Math."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,8]],"date-time":"2020-10-08T21:56:40Z","timestamp":1602194200000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000141\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,30]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["S0963548317000141"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000141","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,30]]}}}