论文标题
在简单多边形中的最小链路可见性路径上
On approximations to minimum link visibility paths in simple polygons
论文作者
论文摘要
我们研究了众所周知的多边形可见性路径（观察者）问题的实用变体。对于多边形$ p $，最低链接可见性路径是$ p $中的多边形可见性路径，其链接数量最少。找到最小链路可见性路径的问题是简单多边形的NP- hard。如果最低链接可见性路径的链接长度（链接数）为$ opt $，用于带有$ n $顶点的简单多边形$ p $，我们提供$ O（kn^2）$运行时的算法，可产生多边形可见性路径（或tours），最多可在$+a_l/k-1 $ a_l/$（k-k-k-1）$ a_l/k）（或$）$（或$）（k-1）$（K）或$ k $是$ p $，$ a_l $的参数，是输出敏感参数，$γ$是$ O（k^3）$ o（k^3）$ time time近似算法的近似因子，用于图形旅行推销员问题（路径或旅游版本）。
We investigate a practical variant of the well-known polygonal visibility path (watchman) problem. For a polygon $P$, a minimum link visibility path is a polygonal visibility path in $P$ that has the minimum number of links. The problem of finding a minimum link visibility path is NP-hard for simple polygons. If the link-length (number of links) of a minimum link visibility path (tour) is $Opt$ for a simple polygon $P$ with $n$ vertices, we provide an algorithm with $O(kn^2)$ runtime that produces polygonal visibility paths (or tours) of link-length at most $(γ+a_l/(k-1))Opt$ (or $(γ+a_l/k)Opt$), where $k$ is a parameter dependent on $P$, $a_l$ is an output sensitive parameter and $γ$ is the approximation factor of an $O(k^3)$ time approximation algorithm for the graphic traveling salesman problem (path or tour version).
