Computing minimum-area rectilinear convex hull and L-shape

摘要

We study the problems of computing two non-convex enclosing shapes with the minimumarea; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, wefind an L-shape enclosing the points or a rectilinear convex hull of the point set withminimum area over all orientations. We show that the minimum enclosing shapes forfixed orientations change combinatorially at most 0(n) times while rotating the coordinatesystem. Based on this, we propose efficient algorithms that compute both shapes with theminimum area over all orientations. The algorithms provide an efficient way of maintainingthe set of extremal points, or the staircase, while rotating the coordinate system, andcompute both minimum enclosing shapes in 0(n~2) time and 0(n) space. We also showthat the time complexity of maintaining the staircase can be improved if we use morespace.