Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations

DOI10.1007/S10898-020-00953-5MaRDI QIDQ2022326zbMATH OpenOpenAlexFDO

Authors Carlos Alegría, David Orden, Carlos Seara, J. Urrutia

Publication date 28 April 2021

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

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

zbMATH Keywords

minimum arearectilinear convex hullrestricted orientation convex hull

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10)

Abstract: Let $P$ be a set of $n$ points in the plane. We compute the value of $hetain[0,2pi)$ for which the rectilinear convex hull of $P$, denoted by $mathcal{RH}_{heta}(P)$, has minimum (or maximum) area in optimal $O(nlogn)$ time and $O(n)$ space, improving the previous $O(n^2)$ bound. Let $mathcalO$ be a set of $k$ lines through the origin sorted by slope and let $alph{a}_i$ be the aperture angles of the $2k$ sectors defined by every pair of two consecutive lines. Let $Thet{a}_i=pi-alph{a}_i$ and $Theta=minThet{a}_i:i=1,ldots,2k$. We further obtain: (1) Given a set $mathcalO$ such that $Thetagefracpi2$, we provide an algorithm to compute the $mathcalO$-convex hull of $P$ in optimal $O(nlogn)$ time and $O(n)$ space, while if $Theta<fracpi2$ the complexities are $O(fracnThetalogn)$ time and $O(fracnTheta)$ space. (2) Given a set $mathcalO$ such that $Thetagefracpi2$, we compute and maintain the boundary of the ${mathcalO}_{heta}$-convex hull of $P$ for $hetain[0,2pi)$ in $O(knlogn)$ time and $O(kn)$ space, or in $O(kfracnThetalogn)$ time and $O(kfracnTheta)$ space if $Theta<fracpi2$. (3) Finally, given a set $mathcalO$ such that $Thetagefracpi2$, we compute the ${mathcalO}_{heta}$-convex hull of $P$ of minimum (or maximum) area over all $hetain[0,2pi)$ in $O(knlogn)$ time and $O(kn)$ space.

Recommendations

• Rectilinear convex hull with minimum area
• Computing minimum-area rectilinear convex hull and L-shape
• Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations
• On the definition and computation of rectilinear convex hulls
• Maximum rectilinear convex subsets

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 193423 (Why is no real title available?)
• Algorithms for Reporting and Counting Geometric Intersections
• Computing D-convex hulls in the plane
• Computing minimum-area rectilinear convex hull and L-shape
• Convex hull properties and algorithms
• Fitting a two-joint orthogonal chain to a point set
• Illumination of Orthogonal Polygons with Orthogonal Floodlights
• On Finding the Maxima of a Set of Vectors
• On functional separately convex hulls
• On the X-Y convex hull of a set of X-Y polygons
• On the \(\mathcal{O}_\beta\)-hull of a planar point set
• On the definition and computation of rectilinear convex hulls
• Preprocessing Steiner problems from VLSI layout
• Reconstructing orthogonal polyhedra from putative vertex sets
• Rectilinear convex hull with minimum area
• Restricted-orientation convexity.
• Separating bichromatic point sets by L-shapes
• Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms

Cited in

(11)

• On the definition and computation of rectilinear convex hulls
• A fast and efficient algorithm for determining the connected orthogonal convex hulls
• A new algorithm for the minimal-area convex enclosure problem
• Rectilinear convex hull of points in 3D and applications
• Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations
• Computing minimum-area rectilinear convex hull and L-shape
• Rotational polygon containment and minimum enclosure using only robust 2D constructions
• Separating bichromatic point sets in the plane by restricted orientation convex hulls
• Shortcut hulls: vertex-restricted outer simplifications of polygons
• On the \(\mathcal{O}_\beta\)-hull of a planar point set
• Rectilinear convex hull with minimum area

This page was built for publication: Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations

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