On the Rectilinear Convex Layers of a Planar Set

In this paper we give an optimalO(nlogn)time and O(n)space algorithm to compute the rectilinear convex layers of a setSofnpoints on the plane. We also compute the rotation ofSthat minimizes the number of rectilinear convex layers inO(n 2 logn)time and O(n 2 )space.