Abstract | ||
---|---|---|
We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in O(n log n) time as compared to the best known algorithm that computes a shortest watchman route which runs in O(n^6) time. |
Year | Venue | Keywords |
---|---|---|
2001 | Fundam. Inform. | constant factor,shortest watchman route,known algorithm,n log n,fast algorithm,simple polygon,watchman route,algorithms,computational geometry,art gallery problem,visibility |
Field | DocType | Volume |
Discrete mathematics,Art gallery problem,Visibility,Combinatorics,Computer science,Computational geometry,Simple polygon,Time complexity | Journal | 45 |
Issue | ISSN | Citations |
3 | 0169-2968 | 1 |
PageRank | References | Authors |
0.35 | 8 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bengt J. Nilsson | 1 | 210 | 24.43 |