Paper by Erik D. Demaine

Reference:

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.

BibTeX

@Article{Snipperclips_CGTA,
  AUTHOR        = {Zachary Abel and Hugo Akitaya and Man-Kwun Chiu and Erik D. Demaine and Martin L. Demaine and Adam Hesterberg and Matias Korman and Jayson Lynch and Andr\'e van Renssen and Marcel Roeloffzen},
  TITLE         = {Snipperclips: Cutting Tools into Desired Polygons using Themselves},
  JOURNAL       = {Computational Geometry: Theory and Applications},
  journalurl    = {https://www.sciencedirect.com/journal/computational-geometry},
  VOLUME        = 98,
  MONTH         = {October},
  YEAR          = 2021,
  PAGES         = {101784},

  length        = {24 pages},
  papers        = {Snipperclips_CCCG2017},
  replaces      = {Snipperclips_CCCG2017},
  doi           = {https://dx.doi.org/10.1016/J.COMGEO.2021.101784},
  dblp          = {https://dblp.org/rec/journals/comgeo/AbelACDDHKLRR21},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.comgeo.2021.101784">ScienceDirect</A>
                   and 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 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.

Comments:

This paper is also available from ScienceDirect and as arXiv:2105.08305.

Length:

The paper is 24 pages.

Availability:

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)