Rectilinear Convex Hull of Points in 3D

Pablo Pérez-Lantero, Carlos Seara, Jorge Urrutia

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 a…