Moving coins (Q2489547)

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.