Rectilinear Convex Hull with Minimum Area
Carlos Alegría-Galicia, Tzolkin Garduño, Rosas-Navarrete Areli, Seara Carlos, Jorge Urrutia · 2012
Abstract. Let P be a set of n points in the plane. We solve the problem of computing an orientation of the plane for which the rectilinear convex hull of P has minimum area in optimal Θ(n log n) time and O(n) space.