Rotational polygon containment and minimum enclosure
Victor Milenkovic · 1998
An algorithm and implementation is given for rotational polygon containment: given polygons P1 ; P2 ; P3 ; : : : ; Pk and a container polygon C, find rotations and translations for the k polygons that place them into the container without overlapping. A version of the algorithm and implementation also solves rotational minimum enclosure: given a class C of container polygons, find a container C 2 C of minimum area for which containment has a solution. Minimum enclosure algorithms are given for the following classes: 1) rectangles of fixed width, 2) scaled copies of a fixed convex polygon, 3) arbitrary rectangles. Containment and minimum enclosure are NP-hard (even in the purely translational case). The minimum enclosure is approximate: it bounds the the minimum area between (1 \\Gamma ffl)A and A. Experiments are done to determine the largest practical value of k for both containment and minimum enclosure. Important applications for these algorithm to industrial problems are discussed...