Translational polygons containment and minimal enclosure using geometric algorithms and mathematical programming

Abstract

We present an algorithm for the two-dimensional translational containment problem: find translations for k polygons (with up to m vertices each) which place them inside a polygonal container (with n vertices) without overlapping. The polygons and container may be nonconvex. The containment algorithm consists of new algorithms for restriction, evaluation, and subdivision of two-dimensional configuration spaces. The restriction and evaluation algorithms both depend heavily on linear programming; hence we call our algorithm an LP containment algorithm. Our LP containment algorithm is distinguished from previous containment algorithms by the way in which it applies principles of mathematical programming and also by its tight coupling of the evaluation and subdivision algorithms. Our new evaluation algorithm a local overlap minimum. Our distance-based subdivision algorithm eliminates a "false" (local but not global) overlap minimum and all layouts near that overlap minimum, allowing the algorithm to make progress towards the global overlap minimum with each subdivision. In our experiments on data sets from the apparel industry, our LP algorithm can solve containment for up to ten polygons in a few minutes on a desktop workstation. Its practical running time is better than our previous containment algorithms and we believe it to be superior to all previous translational containment algorithms. Its theoretical running time, however, depends on the number of local minima visited, which is O((6kmn + k^2m^2)^(2k+1)/k!). To obtain a better theoretical running time, we present a modified (combinatorial) version of LP containment with a running time of O(((6kmn + k^2m^2)^(2k+1)/(k-5)!)logkmn), which is better than any previous combinatorial containment algorithm. For constant k, it is within a factor of log mn of the lower bound. We generalize our configuration space containment approach to solve minimal enclosure problems. We give algorithms to find the minimal enclosing square and the minimal area enclosing rectangle for k translating polygons. Our LP containment algorithm and our minimal enclosure algorithms succeed by combining rather than replacing geometric techniques with linear programming. This demonstrates the manner in which linear programming can greatly increase the power of geometric algorithms.