Empty Monochromatic Simplices

Abstract

Let $S$ be a $k$-colored (finite) set of $n$ points in ${\mathbb{R}}^d$, $d\ge 3$, in general position, that is, no {$(d+1)$} points of $S$ lie in a common $(d-1)$}-dimensional hyperplane. We count the number of empty monochromatic $d$-simplices determined by $S$, that is, simplices which have only points from one color class of $S$ as vertices and no points of $S$ in their interior. For $3\le k\le d$ we provide a lower bound of $\hat{I}\text{c◯}(n^{d-k+1+2^{-d}})$ and strengthen this to $\hat{I}\text{c◯}(n^{d-2/3})$ for $k=2$. On the way we provide various results on triangulations of point sets in ${\mathbb{R}}^d$. In particular, for any constant dimension $d\ge 3$, we prove that every set of $n$ points ($n$ sufficiently large), in general position in ${\mathbb{R}}^d$, admits a triangulation with at least $dn+\hat{I}\text{c◯}(\log n)$ simplices.