L. Prasad et Ss. Iyengar, A NOTE ON THE COMBINATORIAL STRUCTURE OF THE VISIBILITY GRAPH IN SIMPLE POLYGONS, Theoretical computer science, 140(2), 1995, pp. 249-263
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.