Combinatorial aspects of point visibility

Abstract

This dissertation is concerned with the combinatorics of visibility graphs of simple polygons. We seek to obtain combinatorial properties that characterize such visibility graphs. A key algorithmic problem that arises in this context is the reconstruction problem : given a graph as input, construct a simple polygon in the plane, such that the visibility graph of the polygon is isomorphic to the given graph, or halt within a finite amount of time if no such polygon exists. The decision problem for visibility graph recognition is only known to be in PSPACE. Algorithms for the reconstruction problem are known only for a few restricted classes of graphs. We study the relationship between the visibility graph recognition/reconstruction problem and two classical problems in computational synthetic geometry : the co-ordinatizability problem for chirotopes and the realizability problem for circular sequences of permutations. We introduce a class of graphs called Q -Persistent graphs, and show that all visibility graphs of simple polygons are properly contained in this class. We derive additional restrictions that are necessary for a graph in this class to be a visibility graph. We show that for any graph satisfying these necessary conditions, a simplicial chirotope can be constructed by a polynomial time algorithm. The existence of affine co-ordinatizations for these chirotope would imply that every graph in the corresponding class is a visibilty graph, thus characterizing completely, the visibility graphs of simple polygons. Our algorithm may be viewed as solving a combinatorial version of the reconstruction problem for visibility graphs of simple polygons. For the special case of visibility graphs of convex fans, we identify a special subclass called persistent graphs and we develop algorithms that reconstruct the circular sequence of permutations associated with a configuration representing the polygon. Specifically, we show that for any persistent graph, there exists a maximal chain in the weak Bruhat order of the symmetric group associated with the graph. This maximal chain can be recovered from the graph by a polynomial time algorithm. The realizability of the circular sequence associated with this chain, would imply that every persistent graph is the visibility of a convex fan.