Optimizing generalized kernels of polygons
| Autor: | Martinez-Moraian, Alejandra, Orden, David, Palios, Leonidas, Seara, Carlos, Żyliński, Paweł |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Journal of Global Optimization (2021) 80, 887-920 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s10898-021-01020-3 |
| Popis: | 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 $\mathcal{O}$-${\rm Kernel }$ of the polygon $P$, denoted by $\mathcal{O}$-${\rm Kernel }(P)$, is the subset of points which $\mathcal{O}$-see all the other points in $P$. This work initiates the study of the computation and maintenance of $\mathcal{O}$-${\rm Kernel }(P)$ as we rotate the set $\mathcal{O}$ by an angle $\theta$, denoted $\mathcal{O}$-${\rm Kernel }_{\theta}(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 and maintaining the $\mathcal{O}$-${\rm Kernel }_{\theta}(P)$ while $\theta$ varies in $[-\frac{\pi}{2},\frac{\pi}{2})$, obtaining the angular intervals where: (i) $\mathcal{O}$-${\rm Kernel }_{\theta}(P)$ is not empty, (ii) $\mathcal{O}$-${\rm Kernel }_{\theta}(P)$ optimizes area or perimeter. Further, we show how the algorithms can be improved when $P$ is a simple orthogonal polygon. Comment: 26 pages, 18 figures, version submitted to Journal of Global Optimization (the accepted version including minor changes) |
| Databáze: | arXiv |
| Externí odkaz: |
|