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 .
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 .
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 .
The code of the applet is based on this algorithm.
The proof provided is inspired by J. O'Rourke.