Rectilinear Convex Hull of Points in 3D

Abstract

Let $P$ be a set of $n$ points in ${\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)$-time and $O(n)$-space algorithm to compute $RCH(P)$. We also obtain an efficient $O(n{\log }^{2}n)$-time and $O(n\log n)$-space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of $P$ as we rotate ${\mathbb{R}}^3$ around the $z$-axis. Finally we study some properties of the rectilinear convex hulls of point sets in ${\mathbb{R}}^3$.