  Let $P$ be a $k$-colored set of $n$ points in the plane, $4 \leq k \leq n$.
We study the problem of deciding if $P$ contains a subset of four points of
different colors such that its Rectilinear Convex Hull has positive area. We
provide an $O(n \log n)$-time algorithm for this problem, where the hidden
constant does not depend on $k$; then, we prove that this problem has time
complexity $\Omega(n \log n)$ in the algebraic computation tree model. No
general position assumptions for $P$ are required.
