HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/73
Title: Multiple-guard kernels of simple polygons
Authors: Schuierer, Sven
Wood, Derick
Issue Date: Jun-1996
Series/Report no.: Computer Science Technical Report ; HKUST-CS96-20
Abstract: 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].
URI: http://hdl.handle.net/1783.1/73
Appears in Collections:CSE Technical Reports

Files in This Item:

File Description SizeFormat
tr9620.pdf347KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.