# What is the Match-Stick Game in 2D?

You remember playing the match-stick game quite a few years ago with matches you had to remove without disarranging the other ones?...That was in 3D.
What we want to do here is to consider the equivalent game still dealing with matches but now aiming at translating them in the plane only and without crossing any other.

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