Computing minimum-area rectilinear convex hull and \(L\)-shape (Q833717)

Two non-convex problems are considered for computing the minimum area \(L\)-shape and the minimum area rectilinear convex hull of \(n\) points in the plane over all orientations. Using the extremal points, a staircase form is built. The minimum enclosing \(L\)-shape form or the rectilinear convex hull is computed for fixed orientations along the staircases. The staircases are computed in \(\mathcal{O} (n\log n)\) time and the minimum area of the enclosing shapes are computed for a fixed orientation in linear time. It is shown that the algorithm can compute the minimum shapes in quadratic time by preserving the staircases over all orientations.