On the $O_{\beta }$-hull of a planar point set

Abstract

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

References in corpus (1)

• Rectilinear Convex Hull with minimum area

Cited by in corpus (2)

• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets