Multiple translational containment: approximate and exact algorithms
Karen Daniels, Victor Milenkovic · 1995
We present exact algorithms for finding a solution to the twodimensional translational containment problem: find translations for k polygons which place them inside a polygonal container without overlapping. We also give an approximate algorithm: given any ffl, it finds a set of translations such that no point of any polygon is more than 2ffl inside the boundary of any other polygon or outside the container. The term kCN denotes a containment problem in which the k polygons are convex and the container is nonconvex, and kNN denotes nonconvex polygons and container. The polygons have up to m vertices, and the container has n vertices, where n ? m (typically). We give exact algorithms for the following: 2CN in O(mn log n) time, 3CN in O(m 3 n log n) time, and kNN in O((mn) 2k+1 LP(2k; 2kmn + k 2 m 2 )) time, where LP(a; b) is the time to solve a linear program with a variables and b constraints. We present an approximate algorithm for kNN whose running time is O( \\Gamma 1 ...