Angewandte Mathematik Und Informatik Universit at Zu K Oln Approximation Algorithms for Lawn Mowing and Milling Ss Andor P.fekete Center for Parallel Computing Universitt at Zu Kk Oln D{50923 Kk Oln Germany Approximation Algorithms for Lawn Mowing and Milling-猫眼课题宝

DOI：

发表时间：

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

E. Arkin;S. Andor;P. Fekete;Joseph B. M. Mitchell

我们研究了“割草”和“铣削”问题的最短行程/路径问题：给定平面上的一个区域，给定“刀具”的形状（通常是圆形或正方形），以及刀具的最短行程/路径，使得该区域内的每个点都被刀具覆盖在沿行程/路径的某个位置。在铣削版本的问题，刀具被约束留在区域内。在数控口袋加工的自动刀路生成中，难免会出现铣削问题。草坪修剪问题出现在光学检查、喷漆和最优搜索规划中。一般来说，这两个问题都是np困难的。对于这两个问题，我们给出了有效的常因子近似算法。特别地，我们给出了割草问题的（3+）逼近算法和铣削问题的2.5逼近算法。此外，我们给出了简单网格图中TSP问题的一个简单的6 - 5近似算法，从而得到了铣削简单直线多边形的一个11 - 5近似算法。

We study the problem of nding shortest tours/paths for \lawn mowing" and \milling" problems: Given a region in the plane, and given the shape of a \cutter" (typically, a circle or a square), nd a shortest tour/path for the cutter such that every point within the region is covered by the cutter at some position along the tour/path. In the milling version of the problem, the cutter is constrained to stay within the region. The milling problem arises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray painting, and optimal search planning. Both problems are NP-hard in general. We give eecient constant-factor approximation algorithms for both problems. In particular, we give a (3+)-approximation algorithm for the lawn mowing problem and a 2.5-approximation algorithm for the milling problem. Furthermore, we give a simple 6 5-approximation algorithm for the TSP problem in simple grid graphs, which leads to an 11 5-approximation algorithm for milling simple rectilinear polygons.

Angewandte Mathematik Und Informatik Universit at Zu K Oln Approximation Algorithms for Lawn Mowing and Milling Ss Andor P.fekete Center for Parallel Computing Universitt at Zu Kk Oln D{50923 Kk Oln Germany Approximation Algorithms for Lawn Mowing and Milling

文献摘要

被引文献

相似文献