Staircase visibility and computation of kernels

Let be some set of orientations, that is,. We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in. We call such curves-staircases. Two points p andq in a polygonP are said to-see each other if an-staircase fromp toq exists that is completely contained inP. The-kernel of a polygonP is then the set of all points which-see all other points. The-kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the-kernel of a simple polygon, for finite. We also show how to compute theexternal-kernel of a polygon in optimal time. The two algorithms are combined to compute the (-kernel of a polygon with holes in time.This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.