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.