Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Traversing the Machining Graph
verfasst von : Danny Z. Chen, Rudolf Fleischer, Jian Li, Haitao Wang, Hong Zhu
Erschienen in: Algorithms – ESA 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Zigzag pocket machining (or 2
D
-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
(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
log
n
). 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.