Reconstruction Based on Visibility

The thesis investigates geometric compression of graphs and reconstruction of geometric objects based on partial information about them. In the first part we study properties of proximity graphs, such as minimum spanning trees, relative neighborhood graphs, Gabriel graphs, beta-skeletons and Delaunay triangulations, in the constraint setting. Given a plane graph I=(V,E) we find the minimum set S of edges of I such that the edge-constrained proximity graph over the set V of vertices and the set S of constraints contains I. We present efficient algorithms that solve this problem.In the second part, we turn our attention to the probing of convex polygons with a wedge. An omega-wedge consists of two rays emanating from a point and forming an angle omega. Let B be the number of vertices of a convex polygon O whose internal angle is at most omega, (we show that 0<=B<=3). We reconstruct O with B=0 using 2n-2 omega-probes; or 2n-3 omega-probes if omega=90. We show that both results are optimal. We reconstruct O with B=1 (respectively B=2, B=3) using 2n-1 (respectively 2n+3, 2n+5) omega-probes. We prove optimality for the first case and show that the other two cases are almost optimal.The third and the fourth problems revolve around the Art Gallery Localization problem. In the third part we study the problem of placing a set T of broadcast towers in a simple polygon P in order for any point to locate itself in the interior of P. Let V(p) denote the visibility polygon of p. For any point p in P: for each tower t in V(p) the point p receives the coordinates of t and the Euclidean distance between t and p. From this information p can determine its coordinates. We show a tower-positioning algorithm that computes such a set T of size at most 2n/3, where n is the size of P.In the fourth part we study the computational complexity of the Art Gallery Localization problem. We show that determining the minimum number of broadcast towers that can localize a point anywhere in a simple polygon P is NP-hard problem.