Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/73

Multiple-guard kernels of simple polygons

Authors Schuierer, Sven
Wood, Derick
Issue Date 1996-06
Summary A polygon P is k guardable if there are k points in P such that, for all points p in P, there is at least one of the k points that sees p. We call the k points a k-guard set of P and the k-kernel of a polygon P is the union of all k-guard sets of P. We show that the two-kernel of a simple polygon P with n edges has O(n^3) components and that there are polygons with Omega(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-starshaped simple polygon P such that i-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 polygon P is never P itself. For every k >= 1, there are, however, polygons P[k] with holes such that k-kernel(P[k]) = P[k].
Language English
Format Technical report
Access
Files in this item:
File Description Size Format
tr9620.pdf 356086 B Adobe PDF