Optimizing generalized kernels of polygons

DOI10.1007/S10898-021-01020-3MaRDI QIDQ2046316zbMATH OpenOpenAlexFDO

Authors Alejandra Martínez-Moraian, David Orden, Leonidas Palios, Carlos Seara, Paweł Żyliński

Publication date 17 August 2021

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.05995

Mathematics Subject Classification ID

Polyhedra and polytopes; regular figures, division of spaces (51M20) Convex sets in (2) dimensions (including convex curves) (52A10)

Abstract: Let $mathcalO$ 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$ $mathcalO$-emph{sees} $q$ if there is an $mathcalO$-emph{staircase} contained in $P$ that connects $p$ and $q$. The $mathcalO$-$mKernel$ of the polygon $P$, denoted by $mathcalO$-$mKernel(P)$, is the subset of points which $mathcalO$-see all the other points in $P$. This work initiates the study of the computation and maintenance of $mathcalO$-$mKernel(P)$ as we rotate the set $mathcalO$ by an angle $heta$, denoted $mathcalO$-${mKernel}_{heta}(P)$. In particular, we consider the case when the set $mathcalO$ is formed by either one or two orthogonal orientations, $mathcalO=0^{c}irc$ or $mathcalO=0^{c}irc,90^{c}irc$. For these cases and $P$ being a simple polygon, we design efficient algorithms for computing and maintaining the $mathcalO$-${mKernel}_{heta}(P)$ while $heta$ varies in $[-fracpi2,fracpi2)$, obtaining the angular intervals where: (i) $mathcalO$-${mKernel}_{heta}(P)$ is not empty, (ii) $mathcalO$-${mKernel}_{heta}(P)$ optimizes area or perimeter. Further, we show how the algorithms can be improved when $P$ is a simple orthogonal polygon.

Recommendations

• Staircase visibility and computation of kernels
• Dimensions of staircase kernels in orthogonal polygons
• scientific article; zbMATH DE number 176589
• Staircase \(k\)-kernels for orthogonal polygons
• scientific article; zbMATH DE number 140464

Cites work

• A linear algorithm for finding the convex hull of a simple polygon
• An Optimal Algorithm for Finding the Kernel of a Polygon
• Computational geometry. Algorithms and applications.
• Computing common tangents without a separating line
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 1617273 (Why is no real title available?)
• scientific article; zbMATH DE number 140464 (Why is no real title available?)
• Multiple-guard kernels of simple polygons
• On-line construction of the convex hull of a simple polyline

Cited in

(4)

• On the \(\mathcal{O}_\beta\)-hull of a planar point set
• Staircase visibility and computation of kernels
• Separating bichromatic point sets in the plane by restricted orientation convex hulls
• scientific article; zbMATH DE number 140464 (Why is no real title available?)

This page was built for publication: Optimizing generalized kernels of polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2046316)