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 3-space 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 3-space.

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