A NEW ALGORITHM FOR THE 2-POLYGON CONTAINMENT-PROBLEM

This article addresses the two-polygon containment problem. The proble m is to determine if two polygons, denoted P-1 and P-2, can fit inside a fixed polygon Q without overlap. The case when P-1 and P-2 are allo wed to translate and rotate and all three polygons are convex, is cons idered. After characterizing the solution space, an approach utilizing mathematical programming is introduced. An efficient algorithm is dev eloped and implemented for the special case when sides of P-1 and P-2 are matching. The problem is solved by viewing it as a parametric prog ramming problem with a nonlinear parameter. As the algorithm proceeds, optimality conditions (primal feasibility, dual feasibility, and comp lementary slackness) are maintained continuously. The complexity of th e algorithm is O(b(p1 + p2)q), where p1, p2, and q are the numbers of vertices in the polygons, and b is the number of dual bases encountere d (switches in combinations of contacts being maintained) as the angle of rotation ranges through 2 pi radians. The detailed algebraic devel opment, an example, and computational experience are included. (C) 199 7 Elsevier Science Ltd.