Approzimation Algorithms for Cutting Out Polygons with Lines and Rays

摘要：

This paper studies the problem of cutting out a given polygon, drawn on a convex piece of paper, in the cheapest possible way. For the problems of cutting out convex polygons with line cuts and ray cuts, we present a 7.9-approximation algorithm and a 6approximation algorithm, respectively. For the problem of cutting out ray-cuttable polygons, an O (log n)-approximation algorithm is given.

作者: Xuehou Tan

作者单位: Tokai University, 317 Nishino, Numazu 410-0395, Japan

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 534-543

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）