Traversing the Machining Graph

Danny Z. Chen, Rudolf Fleischer, Jian Li, Haitao Wang, Hong Zhu

Abstract

Zigzag pocket machining (or 2D-milling) plays an important role in the manufacturing industry. The objective is to minimize the number of tool retractions in the zigzag machining path for a given pocket (i.e., a planar domain). We give an optimal linear time dynamic programming algorithm for simply connected pockets, and a linear plus O(1)O(h) time optimal algorithm for pockets with h holes. If the dual graph of the zigzag line segment partition of the given pocket is a partial k-tree of bounded degree or a k-outerplanar graph, for a fixed k, we solve the problem optimally in time O(n logn). Finally, we propose a polynomial time algorithm for finding a machining path for a general pocket with h holes using at most OPT+εh retractions, where OPT is the smallest possible number of retractions and ε>0 is any constant.
BibTeX
@inproceedings{chen2006traversing,
  author = {Danny Z. Chen and Rudolf Fleischer and Jian Li and Haitao Wang and Hong Zhu},
  title = {{Traversing the Machining Graph}},
  booktitle = {ESA},
  year = {2006},
  doi = {10.1007/11841036\_22},
}

Loading related content...

Figure