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

  • Danny Z. Chen University of Notre Dame
  • Haitao Wang Utah State University

Abstract

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.
Published
2015-12-21
How to Cite
Chen, D. Z., & Wang, H. (2015). A new algorithm for computing visibility graphs of polygonal obstacles in the plane. Journal of Computational Geometry, 6(1), 316–345. https://doi.org/10.20382/jocg.v6i1a14
Section
Articles