Daniels, KarenLi, ZhenyuMilenkovic, Victor2016-02-041994Daniels, Karen, Zhenyu Li, and Victor Milekovic. 1994. Multiple Containment Methods. Harvard Computer Science Group Technical Report TR-12-94.http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104591We 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.en-USResearch Paper or Report2016-02-04