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 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 n) in the algebraic computation tree model. No general position assumptions for P are required.