Separating Objects in Space
INTRODUCTION
A recurring problem in computer graphics and robot motion planning is to determine if
objects can be separated without colliding. In a video game, one needs to move
representations of people and machines without their images overlapping. An explosion can
be depicted on screen as a simultaneous separation of particles. One may wish to send a
robot through a field of obstacles.
There are many variations within this class of problems. Aside from rare examples such
as the sofa problem in which one attempts to specify the shape of an object which must
follow a specified trajectory, most published problems pertain to moving objects which are
restricted to, for example, spheres, isothetic rectangles, smooth convex bodies, convex
polygons or starshaped polygons. The motion is often limited to translations and
sometimes only to translations parallel to a given line or set of axes. One might inquire
whether a single object can be perturbed without disturbing the others or investigate if
an object can be moved as far apart from the others as desired. Some collections of
objects can only be separated sequentially, others only if subgroups are first separated
and still others only if all are set in motion simultaneously. The answers can vary with
the dimension of the space in which the objects reside. By a theorem of Dawson, any
collection of more than two smooth convex objects in R^{2} can be separated, but
counterexamples exist to the analogous theorem for R^{3}.
The solutions of the above problems engender many more problems. Having determined
theoretically that any collection of a particular class of objects possesses a particular
type of separability, one might still need to develop an efficient algorithm to actually
perform the motion. For example, after determining that a sphere can be distanced along a
line from a set of other spheres if that line does not intersect the contour of the object
formed by unifying all the other spheres, it is a not obvious how to mathematically
represent that contour. One may wish to determine the shortest path (without collisions)
relative to distance or time in directing a robot through a set of obstacles.
DEFINITIONS
Two objects collide if their interiors intersect.
N.B. In all the definitions and theorems below, it will be assumed that,
initially the interiors of the objects of any collection are pairwise disjoint. (i.e.
Their boundaries may intersect.)
A body B is said to be moveable relative to a collection of bodies {O_{a}} if it is possible to effect a continuous sequence of rigid
motions {f(t): 0<=t<=1} with f(0)=B, f(1) is not= B and for all a
and for all t, the interiors f(t) and O_{a} do not
intersect. If, in addition, for all d>0, there exists a continuous family of rigid
motions {f(t):0 <= t <= 1}
with f(0) = B and distance {f(1), B}>= d, B is said to be moveable
to infinity.


Moveable objects not moveable to infinity 
Moveable objects moveable to infinity 
A collection of bodies {B_{i}}_{1 <= i <= n} is movably separable if there exists a sequence
of rigid motions such that for each pair of distinct k and l: 1<=k,l<=n, for each
d>0 eventually distance {B_{k}, B_{l}}>d.
A collection of bodies {B_{i}}_{1 <= i <= n} is interlocked if it is not movably separable .
A collection of bodies {B_{i}}_{1 <= i <= n} is sequentially separable if for all k:
1<=k<=n, B_{k} is moveable to infinity relative to {B_{i}}B_{k}.
As the diagram below illustrates, a collection of bodies can be movably separable without
being sequentially separable.


Objects sequentially separable 
Objects moveably separable but not sequentially
separable 
A collection of bodies {B_{i}}_{1 <= i <= n} is simultaneously movably separable if it is
interlocked but the bodies can still be separated by moving subsets of {B_{i}}_{1
<= i <= n}
simultaneously. (Each such subset includes at least two bodies) The fact that such
collections of objects exist is illustrated by the diagram below and our applet.

Objects simultaneously moveable separable 
A collection of rectangles is isothetic if each of their sides is parallel to a
coordinate axis.

A collection of isothetic rectangles 
A polygon P is described as simple if the only points of the plane that belong to
exactly two edges are the vertices of P and no points of the plane belong to more than two
edges.
A simple polygon is monotone with respect to a line L if for every line m
perpendicular to L the intersection of the polygon with m is connected, i.e. the
intersection must be a line segment, a point, or empty.

Monotone polygon 
If we can find a point x_{0} in a solid body B such that for all x in B, the
line joining x_{0} and x is wholly in B, B is starshaped about x_{0}.
The set of such x_{0} is called the kernel of B.

Star shaped polygon
x_{0} is one of the points of the kernel. It can see any other point inside of the
polygon. 
If for all points x and y in a solid body B, the line joining x and y is wholly in B, B is
convex. Note that convex bodies are starshaped about all their points and monotone
in every direction.

Convex polygon 
An nsided simple polygon is starshaped if n <= 5 and
convex if it is a triangle. (The first observation was employed in the
design of our applet to ensure that the objects the user creates are starshaped. Neither
assertion admits a converse.)
The convex hull of a set of points is the intersection of all possible convex
objects which contain them.
Consider a problem of separating circles in sequence using translations along a certain
direction L. One of the approaches is to sweep a line perpendicular to L from infinity.
The first circle whose center is completely crossed by the sweeping line can be moved to
infinity (circle 1 in the picture). The algorithm is then applied to the remaining
circles. The fact that the sweeping line crosses the center of a circle guarantees an
empty corridor whose width is equal to the circle's diameter.
Next, consider the problem of separating isothetic rectangles along a specified line L.
(L need not be parallel to a coordinate axis) A somewhat different approach may be
suggested. Construct a line of support (see the diagram below) for each rectangle
perpendicular to L. This line of support intersects rectangles A,B,C, and D at the support
vertices a,b,c, and d, respectively. One might suggest that an ordered sets of
translations can be obtained by sorting the projections of the support vertices on L. It
works fine for rectangle B . However, it fails to translate rectangle D, since the latter
is blocked by rectangles A and C although the projection of its support vertex comes
second in the list. Hence this method does not work.

Lines of support a,b,c, and d for isothetic
rectangles A,B,C, and D respectively 
The following method of finding the first rectangle that can be moved in the direction
given can also be applied to translating any set of monotonic polygons in a specified
direction. Given a set of rectangles and a direction in which they are to be translated
consider two sides of each rectangle which intersect at the support vertex. The two line
chain formed by these sides consists of 3 vertices. Rotate the axes such that the Xaxis
is parallel to the direction of translation . The top vertex is the one that has the
largest Ycoordinate relative to the direction of translation . Next imagine that the set
of chains is illuminated by a light bulb positioned at infinity. We assert that the chain
with lowest illuminated top vertex can be moved first in a specified direction. Indeed,
were this not true, (i.e. there is another 2side chain obscuring the selected chain),
then that chain would had the lowest illuminated top vertex.
To determine the translation ordering of a set of any monotonic polygons, start by
isolating a chain of each polygon bounded by the top and bottom vertex (relative to the
direction of translation). This can be done by bringing parallel lines of support from
plus infinity and minus infinty in the direction perpendicular to L until each line
ecounters the first vertex of the polygon on either side. The line sweeping from the top
encounter the top vertex, and the one sweeping from the bottom encounters the bottom
vertex. These two vertices divide the polygonal chain into two subchains. Consider the
subchain whose vertices have a higher Xcoordinate relative to L. Illuminate the obtained
subchains with a light source coming from infinity parallel to L. The subchain with the
lowest illuminated top vertex can be translated in direction L. Proceed in the same manner
for the remaining subchains.


A set of polygons to be translated in direction
L 
Illuminated right polygonal chains. The polygon
with the lowest illuminated top vertex can be moved in the direction L 
Theorem 1 (Robert Dawson 1984)
In any collection of m balls in R^{n}, there exist at least min{m,n+1} balls
which are movable to infinity .
The above result was strengthened by Professor Toussaint.
Theorem 1 A (Godfried Toussaint 1984)
Consider a collection of balls {B_{i}} in R^{n}. Let h (h <= r) be the number of centres of those balls which lie on either
the vertices, edges or faces of the convex hull of {B_{i}}. Then at least h of the
balls are moveable to infinity.

Balls A, B, C, and D are moveable to infinity 
Theorem 2 (Robert Dawson 1984)
In any collection of at least three smooth convex bodies in R^{2}, at least
three elements are movable.

Objects A, B, and C are moveable to infinity 
This theorem, however, is not necessarily true for R^{3 }. Below is a picture
of a convex tile (undergoing rotations around the vertical axis clockwise) which if
connected with similar tiles cannot be pushed out or pushed in. There exists a
configuration of 12 such tiles, such that there is not a single tile which may be moved
without disturbing the others.

Twelve convex tiles, such that there is not one
which may be moved without disturbing the others 
Theorem 3 (Robert Dawson 1984)
Any collection {B_{i}}_{1 <= i <= 1} of starshaped objects in R^{n} is
simultaneously movably separable.
EXAMPLES OF PUZZLES (Prof. Toussaint separates objects using a sequence of
rotations and translations)
Click here for BOMB APPLET
REFERENCES
(1) R.J. Dawson, ''On removing a ball without disturbing the others ,'' Mathematics
Magazine, vol57, no1, January 1984, pp2730.
(2) G.T. Toussaint, ''On translating a set of spheres'', Technical Report SOCS84.4,
School of Computer Science, Mcgill University, March 1984.
(3) G.T. Toussaint, ''Moveable Separability of Sets'', Technical Report No. SOCS84.17,
School of Computer Science, Mcgill University, November 1984.
USEFUL LINKS
(1) Mobility of objects
in space
(2) Jack Snoeyink's
sculpture
SPECIAL THANKS TO
Godfried
T. Toussaint for providing the examples of the puzzles.
