SLIDING DISKS IN THE PLANE
Authors:
- 1 October 2008
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 18 (05) , 373-387
Abstract
Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk slides in the plane without intersecting any other disk, so that its center moves along an arbitrary (open) continuous curve. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. For example, with n congruent disks, [ ] moves always suffice for transforming the start configuration into the target configuration; on the other hand, [ ] moves are sometimes necessary.Keywords
This publication has 3 references indexed in Scilit:
- Moving coinsComputational Geometry, 2006
- Pushing Squares AroundGraphs and Combinatorics, 2006
- Cutting disjoint disks by straight linesDiscrete & Computational Geometry, 1989