Rectilinear Convex Hull of Points in 3d and Applications

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(nlogn) time and O(n) space algorithm to compute RCH(P). We also obtain an efficient O(nlog2n) time and O(nlogn) 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. We study some combinatorial properties of the rectilinear convex hulls of point sets in R3. Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in R3. © The Author(s) 2024.