Rainbow ortho-convex 4-sets in k-colored point sets
<|reference_start|>Rainbow ortho-convex 4-sets in k-colored point sets: 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.<|reference_end|>
@article{flores-peñaloza2024rainbow,
    title={Rainbow ortho-convex 4-sets in k-colored point sets},
    author={David Flores-Pe~naloza (1), Mario A. Lopez (2), Nestaly Mar'in (1),
  David Orden (3) ((1) Departamento de Matem'aticas, Facultad de Ciencias,
  Universidad Nacional Aut'onoma de M'exico, Mexico, (2) Department of
  Computer Science, University of Denver, US, (3) Departamento de F'isica y
  Matem'aticas, Universidad de Alcal'a, Spain)},
    journal={arXiv preprint arXiv:2404.06376},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.06376},
    primaryClass={cs.CG math.CO}
}