Multiple-guard kernels of simple polygons

We study a generalization of the kernel of a polygon. A polygonP isk guardable if there arek points inP such that, for all pointsp inP, there is at least one of thek points that seesp. We call thek points ak-guard set ofP and thek-kernel of a polygonP is the union of allk-guard sets ofP. The usual definition of the kernel of a polygon is now the one-kernel in this notation.We show that the two-kernel of a simple polygonP withn edges has O(n⁴) components and that there are polygons whose two-kernel has (n) components. Moreover, we show that the components of the two-kernel of a simple polygon can be paired in a natural manner which implies that the two-kernel of a simple polygon has either one component or an even number of components. Finally, we consider the question of whether there is a non-star-shaped simple polygonP such that 2-kernel(P) = P. We show that when the two-kernel has only one component, it contains a hole; hence, the two-kernel of a simple polygonP is neverP itself. For everyk 1, there are, however, polygonsP _k with holes such thatk-kernel(P_k) = P_k.This work was supported under grant No. Ot 64/8-1, Diskrete Probleme from the the Deutsche Forschungsgemeinschaft, grants from the Natural Sciences and Engineering Council of Canada, from the Information Technology Research Centre of Ontario, and from the Research Grants Council of Hong Kong.