text: We study the problem of visibility-based exploration, reconstruction and surveillance in the context of supervised learning. Using a level set representation of data and information, we train a convolutional neural network to determine vantage points that maximize visibility. We show that this method drastically reduces the on-line computational cost and determines a small set of vantage points that solve the problem. This enables us to efficiently produce highly-resolved and topologically accurate maps of complex 3D environments. We present realistic simulations on 2D and 3D urban environments.
  @cite_29: We study the computational complexity of the art gallery problem originally posed by Klee, and its variations. Specifically, the problem of determining the minimum number of vertex guards that can see an n -wall simply connected art gallery is shown to be NP-hard. The proof can be modified to show that the problems of determining the minimum number of edge guards and the minimum number of point guards in a simply connected polygonal region are also NP-hard. As a byproduct, the problem of decomposing a simple polygon into a minimum number of star-shaped polygons such that their union is the original polygon is also shown to be NP-hard.
  @cite_21: 
  @cite_1: In 1973, Victor Klee posed the following question: How many guards are necessary, and how many are sufficient to patrol the paintings and works of art in an art gallery with n walls? This wonderfully naive question of combinatorial geometry has, since its formulation, stimulated a plethora of papers, surveys and a book, most of them written in the last fifteen years. The first result in this area, due to V. Chvatal, asserts that n 3 guards are occasionally necessary and always sufficient to guard an art gallery represented by a simple polygon with n vertices. Since ChvataFs result, numerous variations on the art gallery problem have been studied, including mobile guards, guards with limited visibility or mobility, illumination of families of convex sets on the plane, guarding of rectilinear polygons, and others. In this paper, we survey most of these results.
  @cite_27: In this paper we consider the problem of placing guards to supervise an art gallery with holes. No gallery withn vertices andh holes requires more than [(n+h) 3] guards. For some galleries this number of guards is necessary. We present an algorithm which places the [(n+h) 3] guards inO(n2) time.
  @cite_15: Art gallery problems which have been extensively studied over the last decade ask how to station a small (minimum) set of guards in a polygon such that every point of the polygon is watched by at least one guard. The graph-theoretic formulation and solution to the gallery problem for polygons in standard form is given. A complexity analysis is carried out, and open problems are discussed. >
  @cite_17: The inherent computational complexity of polygon decomposition problems is of theoretical interest to researchers in the field of computational geometry and of practical interest to those working in syntactic pattern recognition. Three polygon decomposition problems are shown to be NP-hard and thus unlikely to admit efficient algorithms. The problems are to find minimum decompositions of a polygonal region into (perhaps overlapping) convex, star-shaped, or spiral subsets. We permit the polygonal region to contain holes. The proofs are by transformation from Boolean three-satisfiability, a known NP-complete problem. Several open problems are discussed.
summary: The surveillance problem is related to the art gallery problem in computational geometry, where the task is to determine the minimum set of guards who can together observe a polygonal gallery. Vertex guards must be stationed at the vertices of the polygon, while point guards can be anywhere in the interior. For simply-connected polygonal scenes, Chv 'atal showed that @math vertex guards, where @math is the number of vertices, are sometimes necessary and always sufficient @cite_21 . For polygonal scenes with @math holes, @math point guards are sufficient @cite_27 @cite_15 . However, determining the optimal set of observers is NP-complete @cite_1 @cite_17 @cite_29 .