Recognizing and Reconstructing Pseudo Polygons and Terrains from Their Visibility Graphs

Date
2017
Authors
Ameer, Safwa
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

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.

Description
This item is available only to currently enrolled UTSA students, faculty or staff.
Keywords
Citation
Department
Computer Science