Recognizing and Reconstructing Pseudo Polygons and Terrains from Their Visibility Graphs
The computational geometry community began studying visibility graphs (VGs) over 30 years ago. Today, visibility graphs are essential to cutting edge applications including robotic navigation, self-driving cars, scene analysis, graphics, art gallery problem, signals routing, constructing Maps, pedestrian and vehicles routing, and many other related problems. Unfortunately, theoretical support has not kept pace as some of the most fundamental questions about VGs still have not been solved. It is significant that the research community continue to advance visibility graph knowledge from both theoretical and practical perspectives. In this thesis, we present our contribution in solving VG characterization, recognition, and reconstruction questions for pseudo polygons, and terrains. These three questions have been identified as some of the most important open problems in all of computational geometry, listed as problem 17 in The Open Problems Project.