Optimizing generalized kernels of polygons

Let O be a set of k orientations in the plane, and let P be a simple polygon in the plane. Given two points p, q inside P, we say that p O-sees q if there is an O-staircase contained in P that connects p and q. The O-Kernel of the polygon P, denoted by O-Kernel (P), is the subset of points of P which O-see all the other points in P. This work initiates the study of the computation and maintenance of O-Kernel (P) as we rotate the set O by an angle theta, denoted by O-Kernel(theta) (P). In particular, we consider the case when the set O is formed by either one or two orthogonal orientations, O = {0 degrees} or O = {0 degrees, 90 degrees}. For these cases and P being a simple polygon, we design efficient algorithms for computing the O-Kernel(theta) (P) while theta varies in [-pi/2, pi/2), obtaining: (i) the intervals of angle theta where O-Kernel(theta) (P) is not empty, (ii) a value of angle theta where O-Kernel(theta) (P) optimizes area or perimeter. Further, we show how the algorithms can be improved when P is a simple orthogonal polygon. In addition, our results are extended to the case of a set O = {alpha(1), ..., alpha(k)}.

Automated summary

This study focuses on the computation and maintenance of the O-Kernel within a polygon as the set of orientations O is rotated by an angle theta. Efficient algorithms are designed for cases of one or two orthogonal orientations and simple polygons, determining the intervals of theta where the O-Kernel is not empty and optimizing the area or perimeter at a specific theta value. The algorithms are further improved for simple orthogonal polygons, with results extended to cases where O is a set of multiple orientations.