Balanced 6-holes in 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 $\vert R\vert = \vert B\vert = n$, then the number of balanced 6-holes in $S$ is at least $1/45n^2-\Theta(n)$.

Reference: O. Aichholzer, J. Urrutia, and B. Vogtenhuber. Balanced 6-holes in bichromatic point sets. In Proc. of the $16^{th}$ Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG$^2$ 2013), Tokyo, Japan, 2013.