Rectilinear convex hull of points in 3D and applications

Let P be a set of n points in \(\mathbb {R}^3\) ${\mathbb{R}}^3$ in general position, and let RCH(P) be the rectilinear convex hull of P. In this paper we obtain an optimal \(O(n\log n)\) $O(nlogn)$ time and O(n) space algorithm to compute RCH(P). We also obtain an efficient \(O(n\log ^2 n)\) $O(n{log}^{2}n)$ time and \(O(n\log n)\) $O(nlogn)$ space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate \({\mathbb {R}}^3\) ${\mathbb{R}}^3$ around the Z-axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in \(\mathbb {R}^3\) ${\mathbb{R}}^3$ . Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in \(\mathbb {R}^3\) ${\mathbb{R}}^3$ .