On the O_-hull of a planar point set

DOI10.1016/J.COMGEO.2017.06.003zbMATH Open1385.65021arXiv1509.02601OpenAlexW3103940077MaRDI QIDQ1699299FDOQ1699299

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)

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 $$.

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

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

zbMATH Keywords

fittingconvex hullarea optimizationperimeter optimizationrestricted-orientation geometry

Mathematics Subject Classification ID

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

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
• On Some Distance Problems in Fixed Orientations
• Title not available (Why is that?)
• Restricted-orientation convexity.
• Optimal computation of finitely oriented convex hulls
• 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
• Rectilinear convex hull with minimum area

Cited In (9)

• Set estimation under biconvexity restrictions
• A fast and efficient algorithm for determining the connected orthogonal convex hulls
• Empty squares in arbitrary orientation among points
• Maximum rectilinear convex subsets
• A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set
• Rectilinear convex hull of points in 3D and applications
• Fitting a two-joint orthogonal chain to a point set
• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• Separating bichromatic point sets in the plane by restricted orientation convex hulls

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)