Technical Report No. 40, December 1991 - Abstract

Sven Schuierer, Derick Wood:
Restricted Orientation Visibility

Let O be some set of orientations, that is, O is a subset or equal to [0 deg., 360 deg.). In this paper, we look at the consequences of defining visibility based on curves that are monotone with respect to the orientations in O. We call such curves O-staircases (Os). Two points p and q in a polygon P are said to Os-see each other if there exists an O-staircase from p to q that is completely contained in P. We investigate some of the structural properties of Os-visibility and then turn to the computation of the Os-kernel of a polygon.

The Os-kernel of a polygon P is then the set of all points which Os-see all other points. We show that the Os-kernel of a simple polygon can be obtained as the intersection of all {Theta}-kernels, with Theta in O. With the help of this observation we are able to develop an O(n*log|O|) algorithm to compute the Os-kernel in a simple polygon, for finite O. We also show how to compute the external Os-kernel of a polygon in time O(n + |O|). Both algorithms can be combined to compute the Os-kernel of a polygon with holes in time O(n^2 + n*|O|).