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.
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 .
@cite_29 @cite_21 @cite_1 @cite_27 @cite_15 @cite_17
2063442090 2087422927 2502636724 2030535045 2126369940 1981988453
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. We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT 2). 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. A 1.5-dimensional terrain T with n vertices is an xmonotone polygonal chain in the plane. A point guard p on T guards a point q of T if the line segment connecting p to q lies on or above T ; p is a vertex guard if it is a vertex of T . In the Optimal Terrain Guarding (OTG) problem on T , the objective is to guard the vertices of T by the minimum number of vertex guards. King and Krohn [9] showed that the OTG problem is NP-hard on arbitrary terrains, and [6] gave a PTAS for this problem. In this paper, we introduce directed visibility in which the visibility is directed only at adjacent vertices. We give an O(n)-time algorithm that solves the OTG problem exactly on orthogonal terrains under directed visibility. 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. > We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is NP-hard. For the first two proofs (i.e., vertex guards and boundary guards), we construct a reduction from minimum piercing of 2-intervals. The third proof is somewhat simpler; it is obtained by adapting a known reduction from minimum line cover. We also consider the problem of guarding the vertices of a 1.5D rectilinear terrain. We establish an interesting connection between this problem and the problem of computing a minimum clique cover in chordal graphs. This connection yields a 2-approximation algorithm for the guarding problem. A set @math of points on a terrain, also known as an @math -monotone polygonal chain, is said to guard the terrain if every point on the terrain is seen by a point in @math . Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. Using a reduction from PLANAR 3-SAT we prove that the decision version of this problem is NP-hard. This solves a significant open problem and complements recent positive approximability results for the optimization problem. D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too. We provide an O(log log opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building e-nets of size @math for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Bronnimann and Goodrich to build an approximation algorithm from this e-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension. Past research on art gallery problems has concentrated almost exclusively on bounds on the numbers of guards needed in the worst case in various settings. On the complexity side, fewer results are available. For instance, it has long been known that placing a smallest number of guards for a given input polygon is NP -hard. In this paper we initiate the study of the approximability of several types of art gallery problems. We present the first constant-factor approximation algorithm for a nontrivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an @math -approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit the geometric structure of terrains to obtain a substantially improved approximation algorithm. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . 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. A hidden set is a set of points such that no two points in the set are visible to each other. A hidden guard set is a hidden set which is also a guard set. In this paper we consider the problem for finding hidden sets and hidden guard sets in and around polygons. In particular, we establish bounds on the maximum size of hidden sets, and show that the problem of finding a maximum hidden set is NP-hard. For minimum hidden guard sets, similar results are obtained. Polygon partitions Orthogonal polygons Mobile guards Miscellaneous shapes Holes Exterior visibility Visibility groups Visibility algorithms Minimal guard covers Three-dimensions and miscellany. The problem of searching for mobile intruders in a polygonal region by mobile searchers is considered. A searcher can move continuously inside a polygon holding a flashlight that emits a single ray of light whose direction can be changed continuously. The vision of a searcher at any time instant is limited to the points on the ray. The intruders can move continuously with unbounded speed. We denote by ps(P) the polygon search number of a simple polygon P , which is the number of searchers necessary and sufficient to search P . Let n , r , b , and g be the number of edges, the number of reflex vertices, the bushiness, and the size of a minimum guard set of P , respectively. In this paper we present matching upper and (worst case) lower bounds of 1 + log 3 (2b+1) on ps(P) . Also upper bounds on ps(P) in terms of n,r , and g are presented;ps(P) ≤ 1 + log 3 (n-3) ,ps(P) ≤ 1 + log 3 r , and ps(P) ≤ 2 + log 2 g . These upper bounds are tight or almost tight in the worst case, since we show that for any natural number s 2 , there is a polygon P such that ps(P) = log 3 (n+1) = log 3 (2r+3) = 1 + log 3 (2g-1) = s . Given a polygon @math , for two points @math and @math contained in the polygon, their is the length of the shortest @math -path within @math . A of radius @math centered at a point @math is the set of points in @math whose geodesic distance to @math is at most @math . We present a polynomial time @math -approximation algorithm for finding a densest geodesic unit disk packing in @math . Allowing arbitrary radii but constraining the number of disks to be @math , we present a @math -approximation algorithm for finding a packing in @math with @math geodesic disks whose minimum radius is maximized. We then turn our focus on of @math and present a @math -approximation algorithm for covering @math with @math geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are @math -hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius. An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that @math probes are sufficient to verify a specified n-gon, while for determining convex polygons @math X-ray probes are necessary and @math sufficient, with @math sufficient given that a lower bound on the size of the smallest edge of P is known. The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertex set consists of the vertices of the obstacles and whose edges are pairs of vertices @math such that the open line segment between u and v does not intersect any of the obstacles. The visibility graph is an important combinatorial structure in computational geometry and is used in applications such as solving visibility problems and computing shortest paths. This paper presents an algorithm that computes the visibility graph of a set of obstacles in time @math , where E is the number of edges in the visibility graph and n is the total number of vertices in all the obstacles. In the continuous 1.5-dimensional terrain guarding problem we are given an x-monotone chain (the terrain T ) and ask for the minimum number of point guards (located anywhere on T ), such that all points of T are covered by at least one guard. It has been shown that the 1.5-dimensional terrain guarding problem is NPhard. The currently best known approximation algorithm achieves a factor of 4. For the discrete problem version with a nite set of guard candidates and a nite set of points on the terrain that need to be monitored, a polynomial time approximation scheme (PTAS) has been presented [11]. We show that for the general problem we can construct nite guard and witness sets, G and W , such that there exists an optimal guard cover G G that covers T , and when these guards monitor all points in W the entire terrain is guarded. This leads to a PTAS as well as an (exact) IP formulation for the continuous terrain guarding problem.