Optimizing generalized kernels of polygons

Abstract

Let $\mathcal{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$ $\mathcal{O}$-\emph{sees} $q$ if there is an $\mathcal{O}$-\emph{staircase} contained in $P$ that connects $p$ and~$q$. The \emph{$\mathcal{O}$-Kernel} of the polygon $P$, denoted by $\mathcal{O}$-$\mathrm{kernel}(\mathrm{P})$, is the subset of points of $P$ which $\mathcal{O}$-see all the other points in $P$. This work initiates the study of the computation and maintenance of $\mathcal{O}$-$\mathrm{kernel}(\mathrm{P})$ as we rotate the set $\mathcal{O}$ by an angle $\hat{I}¸$, denoted by $\mathcal{O}$-$\mathrm{kerne}{\mathrm{l}}_{\hat{\mathrm{I}}}¸(\mathrm{P})$. In particular, we consider the case when the set $\mathcal{O}$ is formed by either one or two orthogonal orientations, $\mathcal{O}=\{0^{\circ }\}$ or $\mathcal{O}=\{0^{\circ },90^{\circ }\}$. For these cases and $P$ being a simple polygon, we design efficient algorithms for computing the $\mathcal{O}$-$\mathrm{kerne}{\mathrm{l}}_{\hat{\mathrm{I}}}¸(\mathrm{P})$ while $\hat{I}¸$ varies in $[-\frac{\ddot{I}}{€}2,\frac{\ddot{I}}{€}2)$, obtaining: (i)~the intervals of angle~$\hat{I}¸$ where $\mathcal{O}$-$\mathrm{kerne}{\mathrm{l}}_{\hat{\mathrm{I}}}¸(\mathrm{P})$ is not empty, (ii)~a value of angle~$\hat{I}¸$ where $\mathcal{O}$-$\mathrm{kerne}{\mathrm{l}}_{\hat{\mathrm{I}}}¸(\mathrm{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 $\mathcal{O}=\{\hat{I}{\pm }_1,\dots ,\hat{I}{\pm }_k\}$.

34 pages, 16 figures, accepted version