Rectilinear convex hull of points in 3D and applications

Abstract Let P be a set of n points in R³ 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 n) O (n log n) time and O (n) space algorithm to compute RCH (P). We also obtain an efficient O (n ² n) O (n log 2 n) time and O (n n) O (n log n) space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate {R}³ R 3 around the Z -axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in R³ R 3. Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in R³ R 3.