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, pages 56–61.

BibTeX

@InProceedings{Snipperclips_CCCG2017,
  AUTHOR        = {Erik D. Demaine and Matias Korman and Andr\'e van Renssen and Marcel Roeloffzen},
  TITLE         = {Snipperclips: Cutting Tools into Desired Polygons using Themselves},
  BOOKTITLE     = {Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)},
  bookurl       = {http://2017.cccg.ca/},
  ADDRESS       = {Ottawa, Ontario, Canada},
  MONTH         = {July 26--28},
  YEAR          = 2017,
  PAGES         = {56--61},

  length        = {6 pages},
  papers        = {Snipperclips_CGTA},
  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineKRR17},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/2105.08305">arXiv:2105.08305</A>.},
}

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.

Comments:

This paper is also available as arXiv:2105.08305.

Length:

The paper is 6 pages.

Availability:

The paper is available in PDF (924k).

See information on file formats.

[Google Scholar search]

Related papers:

Snipperclips_CGTA (Snipperclips: Cutting Tools into Desired Polygons using Themselves)