{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T10:01:38Z","timestamp":1768471298973,"version":"3.49.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2017,11,20]],"date-time":"2017-11-20T00:00:00Z","timestamp":1511136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2016-T2-2-154"],"award-info":[{"award-number":["MOE2016-T2-2-154"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["NRF2015VSG-AA3DCM001-014"],"award-info":[{"award-number":["NRF2015VSG-AA3DCM001-014"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation. Prime Minister's Office, Singapore","doi-asserted-by":"crossref","award":["SUTD Digital Manufacturing and Design Centre"],"award-info":[{"award-number":["SUTD Digital Manufacturing and Design Centre"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1565978"],"award-info":[{"award-number":["1565978"]}],"id":[{"id":"10.13039\/100000001","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":[[2017,12,31]]},"abstract":"<jats:p>\n            A geometric dissection is a set of pieces which can be assembled in different ways to form distinct shapes. Dissections are used as recreational puzzles because it is striking when a single set of pieces can construct highly different forms. Existing techniques for creating dissections find pieces that reconstruct two input shapes exactly. Unfortunately, these methods only support simple, abstract shapes because an excessive number of pieces may be needed to reconstruct more complex, naturalistic shapes. We introduce a dissection design technique that supports such shapes by requiring that the pieces reconstruct the shapes only\n            <jats:italic>approximately.<\/jats:italic>\n            We find that, in most cases, a small number of pieces suffices to tightly approximate the input shapes. We frame the search for a viable dissection as a combinatorial optimization problem, where the goal is to search for the best approximation to the input shapes using a given number of pieces. We find a lower bound on the tightness of the approximation for a partial dissection solution, which allows us to prune the search space and makes the problem tractable. We demonstrate our approach on several challenging examples, showing that it can create dissections between shapes of significantly greater complexity than those supported by previous techniques.\n          <\/jats:p>","DOI":"10.1145\/3130800.3130831","type":"journal-article","created":{"date-parts":[[2017,11,22]],"date-time":"2017-11-22T16:25:08Z","timestamp":1511367908000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Approximate dissections"],"prefix":"10.1145","volume":"36","author":[{"given":"Noah","family":"Duncan","sequence":"first","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lap-Fai","family":"Yu","sequence":"additional","affiliation":[{"name":"University of Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sai-Kit","family":"Yeung","sequence":"additional","affiliation":[{"name":"Singapore University of Technology and Design"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Demetri","family":"Terzopoulos","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,11,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"J. Bosboom E.D. Demaine M.L. Demaine J. Lynch P. Manurangsi M. Rudoy and A. Yodpinyanee. 2015. k-Piece dissection is NP-hard. In Abstracts from the 18th Japan Conf. on Discrete and Computational Geometry and Graphs. 2.  J. Bosboom E.D. Demaine M.L. Demaine J. Lynch P. Manurangsi M. Rudoy and A. Yodpinyanee. 2015. k-Piece dissection is NP-hard. In Abstracts from the 18th Japan Conf. on Discrete and Computational Geometry and Graphs. 2."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00181377"},{"key":"e_1_2_1_3_1","volume-title":"Hinged Dissections: Swinging and Twisting","author":"Frederickson G.N.","year":"2002"},{"key":"e_1_2_1_4_1","unstructured":"G.N. Frederickson. 2003. Dissections: Plane and Fancy. Cambridge University Press.  G.N. Frederickson. 2003. Dissections: Plane and Fancy. Cambridge University Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1985-0784187-9"},{"key":"e_1_2_1_6_1","unstructured":"Gurobi Optimization Inc. 2016. Gurobi Optimizer Reference Manual. (2016). http:\/\/www.gurobi.com  Gurobi Optimization Inc. 2016. Gurobi Optimizer Reference Manual. (2016). http:\/\/www.gurobi.com"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2015.07.014"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.345022"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005292125553"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980234"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601224"},{"key":"e_1_2_1_12_1","volume-title":"Discrete and Computational Geometry and Graphs: 18th Japan Conf. (JCDCGG","volume":"9943","author":"Manurangsi P.","year":"2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130803"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3114195.3114663"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276414"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778789"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601173"},{"key":"e_1_2_1_18_1","volume-title":"Proc. Bridges Conf. 49--58","author":"Zhou Y.","year":"2012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925887"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3130800.3130831","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3130800.3130831","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3130800.3130831","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:18Z","timestamp":1750213578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3130800.3130831"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,20]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3130800.3130831"],"URL":"https:\/\/doi.org\/10.1145\/3130800.3130831","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,20]]},"assertion":[{"value":"2017-11-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}