Abstract
An effective and fast algorithm is given for
rotational overlap minimization: given an overlapping layout of polygons
P
1,
P
2,
P
3, …,
P
k
in a container polygon
Q, translate and rotate the polygons to diminish their overlap to a local minimum. A (local) overlap minimum has the property that any perturbation of the polygons increases the overlap. Overlap minimization is modified to create a practical algorithm for
compaction: starting with a non-overlapping layout in a rectangular container, plan a non-overlapping motion that diminishes the length or area of the container to a local minimum. Experiments show that both overlap minimization and compaction work well in practice and are likely to be useful in industrial applications.
