1. Optimizing generalized kernels of polygons
- Abstract
This is a post-peer-review, pre-copyedit version of an article published in Journal of Global Optimization. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10898-021-01020-3, 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 ¿, denoted by O-Kernel¿(P). In particular, we consider the case when the set O is formed by either one or two orthogonal orientations, O={0°} or O={0°,90°}. For these cases and P being a simple polygon, we design efficient algorithms for computing the O-Kernel¿(P) while ¿ varies in [-p2,p2), obtaining: (i) the intervals of angle ¿ where O-Kernel¿(P) is not empty, (ii) a value of angle ¿ where O-Kernel¿(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={a1,…,ak}., This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922, Peer Reviewed, Postprint (author's final draft)
- Published
- 2021