Rectilinear Convex Hull with minimum area

Abstract

Let $P$ be a planar set of $n$ points in general position. We consider the problem of computing an orientation of the plane for which the Rectilinear Convex Hull of $P$ has minimum area. Bae et al. (Computational Geometry: Theory and Applications, Vol. 42, 2009) solved the problem in quadratic time and linear space. We describe an algorithm that reduces this time complexity to $\Theta (n\log n)$.

Cited by in corpus (3)

• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• On the $O_{\beta }$-hull of a planar point set
• An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets