Visibility in Geometry
Visibility problems are explored extensively in discrete mathematics and theoretical computer science and they have many applications in areas such as robotics and rending of images. Given a polygonal region in two or three dimensions, the art gallery problem asks how many guards are needed to "see" all parts of the interior (or exterior). The problems vary in numbers needed as guards are restricted to corners or allowed to stand at any point. Related algorithmic problems are to find locations for the minimum number of guards. In the visibility problem, given a polygon, one wants to find the graph representing what parts of the polygon can be seen (in whole or in part) from each vertex, edge, or face. Efficient construction of these graphs is used to develop efficient computer rendering of scenes represented by polygons, which is a method now being adapted to film-making, architectural rendering, and visualization of objects in computer-aided design. Visibility problems also arise when we seek to program a robot to maneuver through obstacles, and algorithms based on these problems are needed to help us place robots to view all aspects of a hazardous site or to program them to perform different tasks in a manufacturing process.