
Objects That Cannot Be Taken Apart With Two Hands
Jack Snoeyink?
Department of Computer Science
University of British Columbia
Jorge Stolfiy
Department of Computer Science
University of Campinas
Abstract
It has been conjectured that every configuration C of convex objects in 3space with disjoint
interiors can be taken apart by translation with two hands: that is, some proper subset of C
can be translated to infinity without disturbing its complement. We show that the conjecture
holds for five or fewer objects and give a counterexample with six objects. We extend the
counterexample to a configuration that cannot be taken apart with two hands using arbitrary
isometries (rigid motions).
1 Introduction
Have you ever felt, when you were trying to put something together, that you needed an extra hand? In this paper we investigate questions of how many moving subassemblies are necessary to assemble (or by reversing time, disassemble) configurations of convex objects. These questions have applications in the fields of mechanical assembly planning, robotic manipulation, computer graphics, and recreational mathematics, as well as giving insight into the complexity of generalizing from the Euclidean plane to 3space.
Let C be a finite set of convex sets (objects) in Euclidean space Ed. Objects in this paper
always have disjoint interiors. We say that configuration C can be taken apart if some pair of
objects A; B 2 C can be moved arbitrarily far apart by rigid motions of the objects of C such that
the objects always have disjoint interiors. C can be taken apart with k hands if it can be partitioned
into k sets, C = C1 [ ? ? ? [ Ck , and taken apart such that no relative motion occurs inside any Ci.
Finally, configuration C can be taken apart by translation if it can be taken apart using a finite
sequence of translational motions.
?Supported in part by an NSERC Research Grant
yPreviously of DEC Systems Reseach Center, Palo Alto, CA