An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets

Abstract

Let $P$ be a $k$-colored set of $n$ points in the plane, $4\le k\le 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 show this problem to be equivalent to deciding if there exists a point $c$ in the plane such that each of the open quadrants defined by $c$ contains a point of $P$, each of them having a different color. 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 $\hat{I}\text{c◯}(n\log n)$ in the algebraic computation tree model. No general position assumptions for $P$ are required.

17 pages, 4 figures, accepted version