Rainbow ortho-convex 4-sets in k-colored point sets

Let P be a k-colored set of n points in the plane, 4 ≤ k ≤ 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 Ω(n log n) in the algebraic computation tree model. No general position assumptions for P are required.