Empty Monochromatic Simplices

O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, and J. Urrutia

Abstract:

Let $S$ be a $k$-colored (finite) set of $n$ points in ${R}^d$, $d\geq 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 \leq k \leq d$ we provide a lower bound of $\Omega(n^{d-k+1+2^{-d}})$ and strengthen this to $\Omega(n^{d-2/3})$ for $k=2$. On the way we provide various results on triangulations of point sets in ${R}^d$. In particular, for any constant dimension $d\geq 3$, we prove that every set of $n$ points ($n$ sufficiently large), in general position in ${R}^d$, admits a triangulation with at least $dn+\Omega(\log n)$ simplices.

Reference: O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, and J. Urrutia. Empty monochromatic simplices. Discrete & Computational Geometry, 51(2):362-393, 2014.