A linear-time 2-approximation algorithm for the watchman route problem for simple polygons |
| |
Authors: | Xuehou Tan |
| |
Affiliation: | School of High-Technology for Human Welfare, Tokai University, 317 Nishino, Numazu 410-0395, Japan |
| |
Abstract: | Given a simple polygon P of n vertices, the watchman route problem asks for a shortest (closed) route inside P such that each point in the interior of P can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O(n4logn) time, which is too complicated to be suitable in practice. |
| |
Keywords: | Computational geometry Approximation algorithms Watchman route problem Essential cuts Polygon visibility |
本文献已被 ScienceDirect 等数据库收录! |
|