On the performance of maximal intersection of spherical polygons by arcs

An important real-world optimization problem in manufacturing industry is to determine optimal workpiece setups for 4-axis NC machining. In this paper we reveal some interesting relations between this optimal workpiece setup problem and the two classic NP-hard problems in complexity theory (i.e, the vertex cover problem and the set cover problem). These relations immediately show the following results. First the optimal workpiece setup problem is NP-hard. Secondly, the greedy algorithm proposed in [Comput. Aided Des. 35 (2003) pp. 1269-1285] for the optimal workpiece setup problem has the performance ratio bounded by O(ln n-ln ln n+0.78), where n is the number of spherical polygons in the ground set.