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

DOI10.1007/S10898-020-00953-5zbMATH Open1466.52001arXiv1710.10888OpenAlexW3092256677MaRDI QIDQ2022326FDOQ2022326

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

• 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

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)