|
|||||
|
|
Minimum-link watchman tours |
|
| Authors: | Esther M Arkin Joseph S.B Mitchell Christine D Piatko |
| Affiliation: | a Department of Applied Mathematics and Statistics, SUNY, Stony Brook, NY 11794-3600, USA b JHU/APL, Johns Hopkins Road, Laurel, MD 20723-6099, USA |
| Abstract: | We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of O(logn). |
| Keywords: | Link distance Watchman route Polygons NP-complete Approximation algorithms Computational geometry |
| 本文献已被 ScienceDirect 等数据库收录！ | |