Recognizing and Reconstructing Pseudo Polygons and Terrains from Their Visibility Graphs




Ameer, Safwa

Journal Title

Journal ISSN

Volume Title



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.


This item is available only to currently enrolled UTSA students, faculty or staff. To download, navigate to Log In in the top right-hand corner of this screen, then select Log in with my UTSA ID.




Computer Science