Optimizing generalized kernels of polygons
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2018
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915067204730880 |
|---|---|
| author | Martinez-Moraian, Alejandra Orden, David Palios, Leonidas Seara, Carlos Żyliński, Paweł |
| author_facet | Martinez-Moraian, Alejandra Orden, David Palios, Leonidas Seara, Carlos Żyliński, Paweł |
| contents | 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}$-$\rm kernel(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}$-$\rm kernel(P)$ as we rotate the set $\mathcal{O}$ by an angle $θ$, denoted by $\mathcal{O}$-$\rm kernel_θ(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}$-$\rm kernel_θ(P)$ while $θ$ varies in $[-\fracπ{2},\fracπ{2})$, obtaining: (i)~the intervals of angle~$θ$ where $\mathcal{O}$-$\rm kernel_θ(P)$ is not empty, (ii)~a value of angle~$θ$ where $\mathcal{O}$-$\rm 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 $\mathcal{O}=\{α_1,\dots,α_k\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1802_05995 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Optimizing generalized kernels of polygons Martinez-Moraian, Alejandra Orden, David Palios, Leonidas Seara, Carlos Żyliński, Paweł Computational Geometry 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}$-$\rm kernel(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}$-$\rm kernel(P)$ as we rotate the set $\mathcal{O}$ by an angle $θ$, denoted by $\mathcal{O}$-$\rm kernel_θ(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}$-$\rm kernel_θ(P)$ while $θ$ varies in $[-\fracπ{2},\fracπ{2})$, obtaining: (i)~the intervals of angle~$θ$ where $\mathcal{O}$-$\rm kernel_θ(P)$ is not empty, (ii)~a value of angle~$θ$ where $\mathcal{O}$-$\rm 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 $\mathcal{O}=\{α_1,\dots,α_k\}$. |
| title | Optimizing generalized kernels of polygons |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/1802.05995 |