Balanced 6-holes in linearly separable bichromatic point sets

O. Aichholzer, J. Urrutia, and B. Vogtenhuber

Abstract:

We consider an Erdos type question on $k$-holes (empty $k$-gons) in bichromatic point sets. For a bichromatic point set $S = R \cup B$, a balanced $2k$-hole in $S$ is spanned by $k$ points of $R$ and $k$ points of $B$. We show that if $R$ and $B$ are linearly separable and $\vert R\vert = \vert B\vert = n$, then the number of balanced 6-holes in $S$ is at least $1/15n^2-\Theta(n)$.

Reference: O. Aichholzer, J. Urrutia, and B. Vogtenhuber. Balanced 6-holes in linearly separable bichromatic point sets. Electronic Notes in Discrete Mathematics, 44:181 - 186, 2013. Special issue dedicated to LAGOS2013.