{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:35Z","timestamp":1750306715234,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,7,27]],"date-time":"2014-07-27T00:00:00Z","timestamp":1406419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.021.123, 612.001.022"],"award-info":[{"award-number":["639.021.123, 612.001.022"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2014,7,27]]},"abstract":"<jats:p>In this paper we introduce several innovative variants on the classic Connect-The-Dots puzzle. We study the underlying geometric principles and investigate methods for the automatic generation of high-quality puzzles from line drawings.<\/jats:p>\n          <jats:p>Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging \"game play\", making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy.<\/jats:p>\n          <jats:p>Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle --one satisfying the mentioned criteria-- is computationally hard, and present several heuristic algorithms.<\/jats:p>\n          <jats:p>Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.<\/jats:p>","DOI":"10.1145\/2601097.2601224","type":"journal-article","created":{"date-parts":[[2014,7,22]],"date-time":"2014-07-22T15:08:20Z","timestamp":1406041700000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["The Connect-The-Dots family of puzzles"],"prefix":"10.1145","volume":"33","author":[{"given":"Maarten","family":"L\u00f6ffler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mira","family":"Kaiser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"van Kapel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerwin","family":"Klappe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"van Kreveld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Staals","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/gmip.1998.0465"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"volume-title":"Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, IEEE, 617--626","author":"Brodal G. S.","key":"e_1_2_2_3_1"},{"volume-title":"Evolutionary Game Design","author":"Browne C.","key":"e_1_2_2_4_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-2179-4"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25878-7_22"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000058"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/212332.212334"},{"volume-title":"Proceedings of the AISB'02 Symposium on AI and Creativity in the Arts and Science.","year":"2002","author":"Colton S.","key":"e_1_2_2_8_1"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1559\/152304098782383007"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00051-6"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/378583.378612"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195993000257"},{"volume-title":"The Lighter Side of Mathematics: Proceedings of the Eug\u00e9ne Strens Memorial Conference of Recreational Mathematics and its History","author":"Harborth H.","key":"e_1_2_2_14_1"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422956.2422957"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/133994.134011"},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Imai H. and Iri M. 1988. Polygonal approximations of a curve formulations and algorithms. In Computational Morphology Elsevier Science 71--86.  Imai H. and Iri M. 1988. Polygonal approximations of a curve formulations and algorithms. In Computational Morphology Elsevier Science 71--86.","DOI":"10.1016\/B978-0-444-70467-2.50011-4"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-013-0812-6"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(87)80169-X"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2007.08.006"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Paterson M. and \n      Yao F. F\n  . \n  1992\n  . On nearest-neighbor graphs. In ICALP Springer W. Kuich Ed. vol. \n  623\n   of \n  Lecture Notes in Computer Science 416--426.   Paterson M. and Yao F. F. 1992. On nearest-neighbor graphs. In ICALP Springer W. Kuich Ed. vol. 623 of Lecture Notes in Computer Science 416--426.","DOI":"10.1007\/3-540-55719-9_93"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276414"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01334.x"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601097.2601224","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2601097.2601224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:23Z","timestamp":1750231163000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601097.2601224"}},"subtitle":["design and automatic generation"],"short-title":[],"issued":{"date-parts":[[2014,7,27]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7,27]]}},"alternative-id":["10.1145\/2601097.2601224"],"URL":"https:\/\/doi.org\/10.1145\/2601097.2601224","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2014,7,27]]},"assertion":[{"value":"2014-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}