Abstract
Given a two dimensional, non-overlapping layout of convex and non-convex polygons, compaction can be thought of as simulating the motion of the polygons as a result of applied "forces." Compaction can be modeled as a motion of the polygons that reduces the value of some linear functional on their positions. Optimal compaction , planning a motion that finds the global minimum reachable value, is shown to be NP-complete. We give a compaction algorithm that finds a local minimum by direct calculation of the new polygon positions via linear programming. We also consider the related problem of separating overlapping polygons using a minimal amount of motion and show it to be NP-complete. A locally optimum version of this problem is solved using a slight modification of the compaction algorithm. The compaction algorithm and the separation algorithm have been applied to marker making: the task of packing polygonal pieces on a sheet of cloth of fixed width so that total length is minimized. The compaction algorithm has improved cloth utilization of human generated pants markers. The separation algorithm together with a database of human-generated markers can be used to automatically generate markers that are close to human performance.