The basic idea of the game is based
on the movable separability of sets. Given a set of
objects (line segments, circles or simple polygons in 2D), we look for
a sequence of given motions (translations, rotations or both) that will
free the object (e.g. a sofa from a room) or move the entire set.
An overall survey of the topic can be found in G.
T. Toussaint [1].
As regards our problem, we want to translate the whole set of matches considered as line segments, allowing one move at a time. In addition, no collisions are allowed between them. A collision occurs if at some instant two line segments intersect. Since each match thus translated is separated from the initial set, the problem can be viewed as a separability problem.
One question we may first ask is
the following: is it always possible to remove one match (any match) in
translation without going through another match? To answer this
question, we are going to consider one more general problem. Instead of
dealing with line segments, considering the problem of translating rectangles
will give us the answer:
Given a set of n rectangles
and a direction l, a translation ordering always exists
and can be computed in O(nlogn) time, Guibas
and Yao [2].
They also prove this for a set of n convex polygons,
that enables us to state that convex polygons in the plane exhibit the
translation-ordering property.
Consider now a translation in the x-direction. The region
swept by the right boundary of a convex polygon P moving horizontally is
the region swept by a line segment s between a highest and a lowest point
of P. This observation leads to the O(nlogn) algorithm for
translating a set of line segments by Ottman
and Widmayer [3].
The code of the applet is based on this algorithm.
The proof provided is inspired by J. O'Rourke[4].
Fabienne
Lathuilière
Computational
Geometry Page
Student
Projects