Snipperclips: Cutting tools into desired polygons using themselves
Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved. We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e., subt...
| Main Authors: | , , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143963 |
| _version_ | 1811091761579163648 |
|---|---|
| author | Abel, Zachary Akitaya, Hugo Chiu, Man-Kwun Demaine, Erik D Demaine, Martin L Hesterberg, Adam Korman, Matias Lynch, Jayson van Renssen, André Roeloffzen, Marcel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abel, Zachary Akitaya, Hugo Chiu, Man-Kwun Demaine, Erik D Demaine, Martin L Hesterberg, Adam Korman, Matias Lynch, Jayson van Renssen, André Roeloffzen, Marcel |
| author_sort | Abel, Zachary |
| collection | MIT |
| description | Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved. We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e., subtract its current shape from) the other tool. We study the computational problem of, given a target shape represented by a polygonal domain of n vertices, is it possible to create it as one of the tools' shape via a sequence of snip operations? If so, how many snip operations are required? We show that a polynomial number of snips suffice for two different variants of the problem. |
| first_indexed | 2024-09-23T15:07:39Z |
| format | Article |
| id | mit-1721.1/143963 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:07:39Z |
| publishDate | 2022 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1439632023-06-28T20:09:25Z Snipperclips: Cutting tools into desired polygons using themselves Abel, Zachary Akitaya, Hugo Chiu, Man-Kwun Demaine, Erik D Demaine, Martin L Hesterberg, Adam Korman, Matias Lynch, Jayson van Renssen, André Roeloffzen, Marcel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved. We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e., subtract its current shape from) the other tool. We study the computational problem of, given a target shape represented by a polygonal domain of n vertices, is it possible to create it as one of the tools' shape via a sequence of snip operations? If so, how many snip operations are required? We show that a polynomial number of snips suffice for two different variants of the problem. 2022-07-22T14:46:35Z 2022-07-22T14:46:35Z 2021 2022-07-22T14:34:32Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143963 Abel, Zachary, Akitaya, Hugo, Chiu, Man-Kwun, Demaine, Erik D, Demaine, Martin L et al. 2021. "Snipperclips: Cutting tools into desired polygons using themselves." Computational Geometry: Theory and Applications, 98. en 10.1016/J.COMGEO.2021.101784 Computational Geometry: Theory and Applications Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Abel, Zachary Akitaya, Hugo Chiu, Man-Kwun Demaine, Erik D Demaine, Martin L Hesterberg, Adam Korman, Matias Lynch, Jayson van Renssen, André Roeloffzen, Marcel Snipperclips: Cutting tools into desired polygons using themselves |
| title | Snipperclips: Cutting tools into desired polygons using themselves |
| title_full | Snipperclips: Cutting tools into desired polygons using themselves |
| title_fullStr | Snipperclips: Cutting tools into desired polygons using themselves |
| title_full_unstemmed | Snipperclips: Cutting tools into desired polygons using themselves |
| title_short | Snipperclips: Cutting tools into desired polygons using themselves |
| title_sort | snipperclips cutting tools into desired polygons using themselves |
| url | https://hdl.handle.net/1721.1/143963 |
| work_keys_str_mv | AT abelzachary snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT akitayahugo snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT chiumankwun snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT demaineerikd snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT demainemartinl snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT hesterbergadam snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT kormanmatias snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT lynchjayson snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT vanrenssenandre snipperclipscuttingtoolsintodesiredpolygonsusingthemselves AT roeloffzenmarcel snipperclipscuttingtoolsintodesiredpolygonsusingthemselves |