A new algorithm for computing visibility graphs of polygonal obstacles in the plane

Danny Z. Chen, Haitao Wang


Given a set of $h$ pairwise disjoint polygonal obstacles with a total of $n$ vertices in the plane, the vertex-vertex visibility graph is an undirected graph whose nodes are vertices of the obstacles and whose edges are pairs of visible vertices. The vertex-edge and edge-edge visibility graphs are defined similarly. Ghosh and Mount gave a well-known output-sensitive $O(n\log n+k)$ time algorithm for computing these visibility graphs, where $k$ is the size of the corresponding graph. By developing new techniques based on an extended corridor structure, we augment Ghosh and Mount’s algorithm to build these visibility graphs in $O(n+h\log h+k)$ time, after the free space is triangulated. The new algorithm improves Ghosh and Mount’s algorithm by reducing its additive $O(n\log n)$ time factor to $O(n + h\log h)$. Like Ghosh and Mount’s algorithm, our algorithm can also compute several important structures such as the funnel structure and the enhanced visibility graph, which may have other applications.

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v6i1a14

ISSN: 1920-180X