Multiple Containment Methods

Abstract

We present three different methods for finding solutions to the 2D translation-only con- tainment problem: find translations for k polygons that place them inside a given polygonal container without overlap. Both the container and the polygons to be placed in it may be nonconvex. First, we provide several exact algorithms that improve results for k = 2 or k = 3. In particular, we give an algorithm for three convex polygons and a nonconvex container with running time in O(m3nlogmn), where n is the number of vertices in the container, and m is the sum of the vertices of the k polygons. This is an improvement of a factor of n2 over previous algorithms. Second, we give an approximation algorithm for k nonconvex polygons and a nonconvex container based on restriction and subdivision of the configuration space. Third, we develop a MIP (mixed integer programming) model for k nonconvex polygons and a nonconvex container.