On balanced 4-holes in bichromatic point sets

S. Bereg, J. M. Díaz-Báñez, R. Fabila-Monroy, P. Pérez-Lantero, A. Ramírez-Vigueras, T. Sakai, J. Urrutia, I. Ventura

Let $S=R\cup B$ be a point set in the plane in general position such that each of its elements is colored either red or blue, where $R$ and $B$ denote the points colored red and the points colored blue, respectively. A quadrilateral with vertices in $S$ is called a $4$-hole if its interior is empty of elements of $S$. We say that a $4$-hole of $S$ is balanced if it has $2$ red and $2$ blue points of $S$ as vertices. In this paper, we prove that if $R$ and $B$ contain $n$ points each then $S$ has at least $\frac{n^2-4n}{12}$ balanced $4$-holes, and this bound is tight up to a constant factor. Since there are two-colored point sets with no balanced {\em convex} $4$-holes, we further provide a characterization of the two-colored point sets having this type of $4$-holes.

Knowledge Graph



Sign up or login to leave a comment