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/