Adrian Dumitrescu
“Recursive construction for sliding disks”
Digital print, 11" x 5", 2008.
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. One can easily show that 2n moves always suffice, while the above construction shows pairs of configurations that require 2n-o(n) moves for this task, for every sufficiently large n. Disks in the start configuration are white, and disks in the target configuration are shaded.
Adrian Dumitrescu, Associate Professor of Computer Science, Department of Computer Science,University of Wisconsin-Milwaukee, Milwaukee, USA
"Art could come from anywhere. One just wants to be careful and not overlook it."
http://www.cs.uwm.edu/faculty/ad/