HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >
Please use this identifier to cite or link to this item:
|Title: ||Multiple-guard kernels of simple polygons|
|Authors: ||Schuierer, Sven|
|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].|
|Appears in Collections:||CSE Technical Reports|
Files in This Item:
All items in this Repository are protected by copyright, with all rights reserved.