Stock cutting of complicated designs by computing minimal nested polygons

This paper studies the following problem in stock cutting: when it is required to cut out complicated designs from parent material, it is cumbersome to cut out the exact design or shape, especially if the cutting process involves optimization. In such cases, it is desired that, as a first step, the machine cut out a relatively simpler approximation of the original design, in order to facilitate the optimization techniques that are then used to cut out the actual design. This paper studies this problem of approximating complicated designs or shapes. The problem is defined formally first and then it is shown that this problem is equivalent to the Minimal Nested Polygon problem in geometry. Some properties of the problem are then shown and it is demonstrated that the problem is related to the Minimal Turns Path problem in geometry. With these results, an efficient approximate algorithm is obtained for the original stock cutting problem. Numerical examples are provided to illustrate the working of the algorithm in different cases.