Containment Algorithms for Nonconvex Polygons with Applications to Layout

Abstract

Layout and packing are NP-hard geometric optimization problems of practical importance for which finding a globally optimal solution is intractable if P6=NP. Such problems appear in industries such as aerospace, ship building, apparel and shoe manufacturing, furniture production, and steel construction. At their core, layout and packing problems have the common geometric feasibility problem of containment: find a way of placing a set of items into a container. In this thesis, we focus on containment and its applications to layout and packing problems. We demonstrate that, although containment is NP-hard, it is fruitful to: 1) develop algorithms for containment, as opposed to heuristics, 2) design containment algorithms so that they say "no" almost as fast as they say "yes", 3) use geometric techniques, not just mathematical programming techniques, and 4) maximize the number of items for which the algorithms are practical. Our approach to containment is based on a new restrict/evaluate/subdivide paradigm. We develop new theory and practical techniques for the operations within the paradigm. The techniques are appropriate for two-dimensional containment problems in which the items and container may be irregular (i.e. nonconvex) polygons and have multiple components, and in which the items may be translated, but not rotated. Our techniques can be combined to form a variety of two-dimensional translational containment algorithms. The paradigm is designed so that, unlike existing iteration-based algorithms, containment algorithms based on the paradigm are adept at saying \no", even for slightly infeasible problems. Infeasible problems occur frequently in practice. We present two algorithms based on our paradigm. We obtain the first practical running times for NP-complete two-dimensional translational containment problems for up to ten nonconvex items in a nonconvex container. Most of our examples are from apparel manufacturing. Typically, each item has from 4 to 100 vertices and the container has from 100 to 300 vertices. We demonstrate that viewing containment as a feasibility problem has many benefits for packing and layout problems. For example, we present an effective method for finding minimal enclosures which uses containment to perform binary search on a parameter. Compaction techniques can accelerate the search. We also use containment to develop the first practical pre-packing strategy for a multi-stage pattern layout problem in apparel manufacturing. Pre-packing is a layout method which packs items into a collection of containers by first generating groups of items which fit into each container and then assigning groups to containers.