On the Rectilinear Convex Layers of a Planar Set
Canek Peláez, Adriana Ramírez-Vigueras, Carlos Seara, Jorge Urrutia · 2012
In this paper we give an optimal O(n log n) time and O(n) space algorithm to compute the rectilinear convex layers of a set S of n points on the plane. We also compute the rotation of S that minimizes the number of rectilinear convex layers in O(n 2 log n) time and O(n 2) space. 1