Moving coins (Q2489547)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5020734
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Moving coins |
scientific article; zbMATH DE number 5020734 |
Statements
Moving coins (English)
0 references
28 April 2006
0 references
The authors consider combinatorial and computational issues that are related to the problem of moving coins from one configuration to another. Coins are defined as nonoverlapping discs, and moves are defined as collision free translations, all in the Euclidean plane. The problem is motivated by measuring the difference between various configurations. Using a directed graph, authors obtain combinatorial bounds on the number of moves that are necessary and/or sufficient to move coins from one configuration to another. They also consider several decision problems related to coin moving, and obtain some results regarding their computational complexity.
0 references
directed graph
0 references
Hamilton path
0 references
moving coins
0 references
configuration
0 references
collision free translations
0 references
combinatorial bounds
0 references
computational complexity
0 references
0 references
0 references
0 references
0.7972254
0 references
0 references
0 references
