Name
Abstract | ||
|---|---|---|
We consider a restricted version of the art gallery problem within simple polygons in whichthe guards are required to lie on a given one-dimensional object, a watchman route. We callthis problem the vision point problem. We prove the following.ffl The original art gallery problem is NP-hard for the very restricted class of street polygons.ffl The vision point problem can be solved eOEciently for the class of street polygons.ffl A linear time algorithm for the vision point problem exists ... |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/PL00009271 | Algorithmica |
Keywords | Field | DocType |
Key words. Computational geometry,Algorithms,Art gallery problems. | Discrete mathematics,Art gallery problem,Combinatorics,Polygon,Polygon (computer graphics),Computational geometry,Mathematics | Journal |
Volume | Issue | ISSN |
24 | 1 | 0178-4617 |
Citations | PageRank | References |
7 | 0.49 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Carlsson | 1 | 764 | 90.17 |
| Bengt J. Nilsson | 2 | 210 | 24.43 |