### 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|)*.

report40.ps.gz