Name
Abstract | ||
|---|---|---|
In this paper we consider the problem of finding shortest routes from which every point in a given space is visible (watchman routes). We show that the problem is NP-hard when the space is a polygon with holes even if the polygon and the holes are convex or rectilinear. The problem remains NP-hard for simple polyhedra. We present O(n) and O(nlogn) algorithms to find a shortest route in a simple rectilinear monotone polygon and a simple rectilinear polygon respectively, where n is the number of vertices in the polygon. Finding optimum watchman routes in simple polygons is closely related to the problem of finding shortest routes that visit a set of convex polygons in the plane in the presence of obstacles. We show that finding a shortest route that visits a set of convex polygons is NP-hard even when there are no obstacles. We present an O(logn) algorithm to find the shortest route that visits a point and two convex polygons, where n is the total number of vertices. |
Year | DOI | Venue |
|---|---|---|
1986 | 10.1016/0020-0190(88)90141-X | Information Processing Letters |
Keywords | Field | DocType |
simple polyhedron,total number,simple rectilinear monotone polygon,shortest route,optimum watchman route,convex polygon,simple rectilinear polygon,watchman route,simple polygon | Discrete mathematics,Combinatorics,Polygon,Computational geometry,Watchman route problem,Mathematics | Conference |
Volume | Issue | ISSN |
28 | 1 | 0020-0190 |
ISBN | Citations | PageRank |
0-89791-194-6 | 69 | 13.50 |
References | Authors | |
10 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| weipang chin | 1 | 69 | 13.50 |
| Simeon C. Ntafos | 2 | 599 | 98.18 |