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.
Bibliographical noteFunding Information:
An extended abstract of this paper appeared in the proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)  . M. C. was supported by ERC StG 757609 . M. K. was partially supported by MEXT KAKENHI Nos. 12H00855 , and 17K12635 . M.-K. C., M. R. and A. v. R. were supported by JST ERATO Grant Number JPMJER1201 , Japan.
- Cutting tool
- Puzzle game
- Shape matching