Empty Monochromatic Simplices

Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl*, Clemens Huemer, Jorge Urrutia

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Let S be a k-colored (finite) set of n points in Rd, d≥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≤k≤d we provide a lower bound of Ω(nd−k+1+2−d)
and strengthen this to Ω(n d−2/3) for k=2.

On the way we provide various results on triangulations of point sets in Rd
. In particular, for any constant dimension d≥3, we prove that every set of n points (n sufficiently large), in general position in Rd, admits a triangulation with at least dn+Ω(logn) simplices.
Original languageEnglish
Pages (from-to)362-393
JournalDiscrete & Computational Geometry
Issue number2
Publication statusPublished - 2014

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Theoretical

Cite this