EFFICIENT ALGORITHMS FOR SOLVING DIAGONAL VISIBILITY PROBLEMS IN A SIMPLE POLYGON
Soo-Hwan Kim, Sung Yong Shin, Kyung‐Yong Chwa · International Journal of Computational Geometry & Applications · 1995
A diagonal guard is a guard capable of moving along an edge or an internal diagonal in a polygon. A polygon which can be guarded by a diagonal guard is called diagonal-visible. We consider the following three problems concerning the diagonal visibility in a polygon P. First, determine whether or not a guard diagonal exists in P, i.e., P is diagonal-visible. Second, compute all guard diagonals of P. Third, given a query diagonal, determine whether or not it is a guard diagonal. For these problems, we construct a data structure for keeping all guard diagonals in O(n log n) time and O(n) space. Using this data structure, we show that these problems can be solved in O(n log n), O(n log n+k), and O(1) time, respectively, where k is the number of guard diagonals.