Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/73
Multipleguard kernels of simple polygons
Authors 
Schuierer, Sven
Wood, Derick 


Issue Date  199606  
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 kguard set of P and the kkernel of a polygon P is the union of all kguard sets of P. We show that the twokernel 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 twokernel of a simple polygon can be paired in a natural manner which implies that the twokernel of a simple polygon has either one component or an even number of components. Finally, we consider the question of whether there is a nonstarshaped simple polygon P such that ikernel(P) = P. We show that when the twokernel has only one component, it contains a hole; hence, the twokernel of a simple polygon P is never P itself. For every k >= 1, there are, however, polygons P[k] with holes such that kkernel(P[k]) = P[k].  
Language  English 

Format  Technical report  
Access 
Files in this item:
