{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T06:59:56Z","timestamp":1769065196576,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T00:00:00Z","timestamp":1684800000000},"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":["J. ACM"],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n            We introduce the abstract notion of a chain, which is a sequence of\n            <jats:italic>n<\/jats:italic>\n            points in the plane, ordered by\n            <jats:italic>x<\/jats:italic>\n            -coordinates, so that the edge between any two consecutive points is unavoidable as far as triangulations are concerned. A general theory of the structural properties of chains is developed, alongside a general understanding of their number of triangulations.\n          <\/jats:p>\n          <jats:p>\n            We also describe an intriguing new and concrete configuration, which we call the Koch chain due to its similarities to the Koch curve. A specific construction based on Koch chains is then shown to have \u03a9 (9.08\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ) triangulations. This is a significant improvement over the previous and long-standing lower bound of \u03a9 (8.65\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ) for the maximum number of triangulations of planar point sets.\n          <\/jats:p>","DOI":"10.1145\/3585535","type":"journal-article","created":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T12:02:48Z","timestamp":1677499368000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Chains, Koch Chains, and Point Sets with Many Triangulations"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-6838-2628","authenticated-orcid":false,"given":"Daniel","family":"Rutschmann","sequence":"first","affiliation":[{"name":"Department of Computer Science, ETH Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9556-8528","authenticated-orcid":false,"given":"Manuel","family":"Wettstein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2023,5,23]]},"reference":[{"key":"e_1_3_1_2_2","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry","author":"Aichholzer Oswin","year":"2016","unstructured":"Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. 2016. An improved lower bound on the minimum number of triangulations. In Proceedings of the 32nd International Symposium on Computational Geometry."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0704-5"},{"key":"e_1_3_1_4_2","series-title":"North-Holland Mathematics Studies","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/S0304-0208(08)73484-4","volume-title":"Theory and Practice of Combinatorics","author":"Ajtai Mikl\u00f3s","year":"1982","unstructured":"Mikl\u00f3s Ajtai, V\u00e1clav Chv\u00e1tal, Monroe M. Newborn, and Endre Szemer\u00e9di. 1982. Crossing-free subgraphs. In Theory and Practice of Combinatorics. North-Holland Mathematics Studies, Vol. 60. North-Holland, 9\u201312."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462392"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2016.12.002"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00111-6"},{"key":"e_1_3_1_9_2","volume-title":"Proceedings of the 9th Canadian Conference on Computational Geometry","author":"Denny Markus","year":"1997","unstructured":"Markus Denny and Christian Sohler. 1997. Encoding a triangulation as a permutation of its point set. In Proceedings of the 9th Canadian Conference on Computational Geometry."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/110849407"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/189443.189446"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212032"},{"key":"e_1_3_1_13_2","article-title":"Counting triangulations of almost-convex polygons","volume":"45","author":"Hurtado Ferran","year":"1997","unstructured":"Ferran Hurtado and Marc Noy. 1997. Counting triangulations of almost-convex polygons. Ars Comb. 45 (1997), 169--179.","journal-title":"Ars Comb."},{"key":"e_1_3_1_14_2","article-title":"Catalan numbers","author":"Inc. OEIS Foundation","year":"2021","unstructured":"OEIS Foundation Inc. 2021. Catalan numbers. In The On-line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A000108.","journal-title":"The On-line Encyclopedia of Integer Sequences"},{"key":"e_1_3_1_15_2","article-title":"Large Schr\u00f6der numbers","author":"Inc. OEIS Foundation","year":"2021","unstructured":"OEIS Foundation Inc. 2021. Large Schr\u00f6der numbers. In The On-line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A006318.","journal-title":"The On-line Encyclopedia of Integer Sequences"},{"key":"e_1_3_1_16_2","article-title":"Little Schr\u00f6der numbers","author":"Inc. OEIS Foundation","year":"2021","unstructured":"OEIS Foundation Inc. 2021. Little Schr\u00f6der numbers. In The On-line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A001003.","journal-title":"The On-line Encyclopedia of Integer Sequences"},{"key":"e_1_3_1_17_2","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry","author":"Marx D\u00e1niel","year":"2016","unstructured":"D\u00e1niel Marx and Tillmann Miltzow. 2016. Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems. In Proceedings of the 32nd International Symposium on Computational Geometry."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00010-9"},{"key":"e_1_3_1_19_2","volume-title":"On Chains and Point Configurations with Many Triangulations","author":"Rutschmann Daniel","year":"2021","unstructured":"Daniel Rutschmann. 2021. On Chains and Point Configurations with Many Triangulations. Master\u2019s thesis. ETH Zurich, Z\u00fcrich, Switzerland."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00002-5"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009823"},{"issue":"1","key":"e_1_3_1_22_2","article-title":"Counting triangulations of planar point sets","volume":"18","author":"Sharir Micha","year":"2011","unstructured":"Micha Sharir and Adam Sheffer. 2011. Counting triangulations of planar point sets. Electron. J. Comb. 18, 1 (2011), 1--74.","journal-title":"Electron. J. Comb."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137898"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/915627"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3585535","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3585535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:08Z","timestamp":1750178768000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3585535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,23]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3585535"],"URL":"https:\/\/doi.org\/10.1145\/3585535","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,23]]},"assertion":[{"value":"2022-05-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}