• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE International Conference on Computer-Aided Design and Computer Graphics >On the performance of maximal intersection of spherical polygons by arcs
【24h】

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.
机译：制造业中一个重要的真实优化问题是确定4轴NC加工的最佳工件设置。在本文中，我们揭示了这种最佳工件设置问题与复杂性理论中的两个经典的NP难题之间的一些有趣关系（即顶点覆盖问题和设定封面问题）。这些关系立即显示出以下结果。首先，最佳工件设置问题是NP-HARD。其次，[计算机中提出的贪婪算法。辅助des。 35（2003）PP。1269-1285]对于最佳工件设置问题，具有由O（LN N-LN LN N + 0.78）有界限的性能比，其中N是地面组中的球形多边形的数量。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号