A NOTE ON THE COMBINATORIAL STRUCTURE OF THE VISIBILITY GRAPH IN SIMPLE POLYGONS

Combinatorial structure of visibility is probably one of the most fasc inating and interesting areas of engineering and computer science. The usefulness of visibility graphs in computational geometry and robotic navigation problems like motion planning, unknown-terrain learning, s hortest-path planning, etc., cannot be overstressed. The visibility gr aph, apart from being an important data structure for storing and upda ting geometric information, is a valuable mathematical tool in probing and understanding the nature of shapes of polygonal and polyhedral ob jects. In this research we wish to initially focus our attention on a fundamental class of geometric objects. These geometric objects may be looked upon as building blocks for more complex geometric objects, an d which offer an ideal balance between complexity and simplicity, name ly simple polygons. A major theme of the proposed paper is the investi gation of the combinatorial structure of the visibility graph. More im portantly, the goals of this paper are: (i) To characterize the visibi lity graphs of simple polygons by obtaining necessary and sufficient c onditions a graph must satisfy to qualify for the visibility graph of a simple polygon (ii) To obtain hierarchical relationships between vis ibility graphs of simple polygons of a given number of vertices by tre ating them as representing simple polygons that are deformations of on e another. (iii) To exploit the potential of complete graphs to be nat ural coordinate systems for addressing the problem of reconstructing a simple polygon from visibility graph. We intend to achieve this by de fining appropriate ''betweenness'' relationships on points with respec t to the edges of the complete graphs.