Rectilinear Convex Hull of Points in 3D

09/13/2022

∙

by   Pablo Pérez-Lantero, et al.

∙

0

∙

share

Let P be a set of n points in ℝ^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)-time and O(n)-space algorithm to compute RCH(P). We also obtain an efficient O(nlog^2 n)-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 ℝ^3 around the z-axis. Finally we study some properties of the rectilinear convex hulls of point sets in ℝ^3.