Rectilinear convex hull of points in 3D and applications

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(nlog n) O ( n log n ) time and O ( n ) space algorithm to compute RCH ( P ). We also obtain an efficient O(nlog ² n) O ( n log 2 n ) time and O(nlog 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 .