On the O_-hull of a planar point set

DOI10.1016/J.COMGEO.2017.06.003MaRDI QIDQ1699299zbMATH OpenOpenAlexFDO

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

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

area optimizationconvex hullfittingperimeter optimizationrestricted-orientation geometry

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: We study the $$-hull of a planar point set, a generalization of the Orthogonal Convex Hull where the coordinate axes form an angle $$. Given a set $P$ of $n$ points in the plane, we show how to maintain the $$-hull of $P$ while $$ runs from $0$ to $pi$ in $O(nlogn)$ time and $O(n)$ space. With the same complexity, we also find the values of $$ that maximize the area and the perimeter of the $$-hull and, furthermore, we find the value of $$ achieving the best fitting of the point set $P$ with a two-joint chain of alternate interior angle $$.

Review text

The authors present an algorithm to maintain the \(\mathcal{O}_\beta\)-hull of a planar point set while \(\beta\) runs from z to \(\pi\) and extend the result to solve related optimization problems. The values of \(\beta\) that maximize the area and the perimeter of \(\mathcal{O}_\beta H(P)\) are found. A variation of the 2-fitting problem is solved by fitting a two-joint not-necessarily orthogonal polygon chain to a point set.

Recommendations

• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• Fitting a two-joint orthogonal chain to a point set
• Optimizing generalized kernels of polygons
• Rectilinear convex hull with minimum area
• Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations

Cites work

• Computing D-convex hulls in the plane
• Computing minimum-area rectilinear convex hull and L-shape
• Fitting a two-joint orthogonal chain to a point set
• scientific article; zbMATH DE number 4062042 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• On Finding the Maxima of a Set of Vectors
• On Some Distance Problems in Fixed Orientations
• On the definition and computation of rectilinear convex hulls
• Optimal computation of finitely oriented convex hulls
• Rectilinear convex hull with minimum area
• Restricted-orientation convexity.
• Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms

Cited in

(13)

• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set
• A fast and efficient algorithm for determining the connected orthogonal convex hulls
• Separating bichromatic point sets in the plane by restricted orientation convex hulls
• Empty squares in arbitrary orientation among points
• Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms
• Set estimation under biconvexity restrictions
• Maximum rectilinear convex subsets
• Fitting a two-joint orthogonal chain to a point set
• Rectilinear convex hull of points in 3D and applications
• Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles
• An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets
• Efficient real-time and parallel algorithm for connected orthogonal convex hulls on large point sets

This page was built for publication: On the \(\mathcal{O}_\beta\)-hull of a planar point set

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