Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Computing Vision Points in Polygons
| |
|
Computing Vision Points in Polygons
S. Carlsson1 and B. J. Nilsson2
| (1) |
Department of Computer Science, Luleå University of Technology, 971 87 Luleå, Sweden., SE |
| (2) |
Department of Computer Science, Lund University, Box 118, 221 00 Lund, Sweden., SE |
Abstract. We consider a restricted version of the art gallery problem within simple polygons in which the guards are required to lie
on a given one-dimensional object, a watchman route. We call this problem the vision
point
problem . We prove the following:
• The original art gallery problem is NP-hard for the very restricted class of street polygons.
• The vision point problem can be solved efficiently for the class of street polygons.
• A linear time algorithm for the vision point problem exists for the subclass of street polygons called straight
walkable polygons.
Key words. Computational geometry, Algorithms, Art gallery problems.
Received June 6, 1996; revised September 12, 1997.
Fulltext Preview (Small, Large)
|
|
|
|
|
|