Paper by Erik D. Demaine
- Zachary Abel, Hugo Akitaya, Man-Kwun Chiu, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jayson Lynch, André van Renssen, and Marcel Roeloffzen, “Snipperclips: Cutting Tools into Desired Polygons using Themselves”, Computational Geometry: Theory and Applications, volume 98, October 2021, pages 101784.
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 consider several variants of the
problem (such as allowing the tools to be disconnected and/or using an undo
operation) and bound the number of operations needed for each of the variants.
- This paper is also available from ScienceDirect and as arXiv:2105.08305.
- The paper is 24 pages.
- The paper is available in PDF (1195k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Snipperclips_CCCG2017 (Snipperclips: Cutting Tools into Desired Polygons using Themselves)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by