Paper by Erik D. Demaine

Reference:
Erik D. Demaine, Matias Korman, André van Renssen, and Marcel Roeloffzen, “Snipperclips: Cutting Tools into Desired Polygons using Themselves”, in Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), Ottawa, Ontario, Canada, July 26–28, 2017, to appear.

Abstract:
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.

Length:
The paper is 6 pages.

Availability:
The paper is available in PDF (924k).
See information on file formats.
[Google Scholar search]


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 21, 2017 by Erik Demaine.