Partitioning polygons into disjoint axisparallel strips

Abstract

A relevant problem for manufacturing is that of finding a minimum-turn path that covers a surface. One way of doing this is by converting the surface into a grid adhering polygon and partitioning it into single-width rectangles, or “strips”. The focus of this thesis is on finding such a partition that contains the minimum number of strips. For this an approximation algorithm is developed which finds a strip parti tion in polynomial time, with an approximation ratio that depends upon properties of the problem instance. The results also include analysis of the problem in the form of multiple lower bounds on the number of strips in optimal partitions, as well as proving certain properties of optimal solutions. The latter is done by introducing the concept of “switchlines”: lines that separate strip regions of different orientations. Depending on the shape of said lines, it is possible to make claims on the optimality of a solution. The analysis also lays a foun dation for the development of future algorithms to further improve the effectiveness and accuracy in solving this problem.