Rectilinear Convex Hull of Points in 3d

Let P be a set of n points in R3 in general position, and let RCH(P) be the rectilinear convex hull of P. In this paper we obtain an optimal O(nlog n) -time and O(n)-space algorithm to compute RCH(P). We also obtain an efficient O(nlog2n) -time and O(nlog n) -space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate R3 around the z-axis. Finally we study some properties of the rectilinear convex hulls of point sets in R3. © 2020, Springer Nature Switzerland AG.