Snipperclips
| Autor: | André van Renssen, Jayson Lynch, Adam Hesterberg, Man-Kwun Chiu, Erik D. Demaine, Zachary Abel, Martin L. Demaine, Hugo A. Akitaya, Marcel Roeloffzen, Matias Korman |
|---|---|
| Přispěvatelé: | Applied Geometric Algorithms |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Sequence Control and Optimization Theoretical computer science Current (mathematics) 010102 general mathematics Shape matching 0102 computer and information sciences Undo 01 natural sciences Computer Science Applications Domain (software engineering) Computational Mathematics Computational Theory and Mathematics Puzzle game 010201 computation theory & mathematics Cutting tool Computer Science - Computational Geometry Geometry and Topology 0101 mathematics Computational problem Mathematics |
| Zdroj: | Computational Geometry, 98:101784. Elsevier |
| ISSN: | 0925-7721 |
| DOI: | 10.1016/j.comgeo.2021.101784 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect