Traversing the machining graph of a pocket

A simple and linear-time algorithm is presented for solving the problem of traversing a machining graph with minimum retractions encountered in zigzag pocket machining and other applications. This algorithm finds a traversal of the machining graph of a general pocket P with N_h holes, such that the number of retractions in the traversal is no greater than OPT+N_h+N_r, where OPT is the (unknown) minimum number of retractions required by any algorithm and N_r is the number of reducible blocks in P (to be defined in the paper). When the step-over distance is small enough relative to the size of P, N_r becomes zero, and our result deviates from OPT by at most the number of holes in P, a significant improvement over the upper bound 5OPT+6N_h achieved [Proceedings of the Seventh ACM-SIAM Symposium on Discrete Algorithms, 1996; Algorithmica 2000 (26) 19]. In particular, if N_h is zero as well, i.e. when P has no holes, the proposed algorithm outputs an optimal solution. A novel computational modeling tool called block transition graph is introduced to formulate the traversal problem in a compact and concise form. Efficient algorithms are then presented for traversing this graph, which in turn gives rise to the major result.