On the Size of Chromatic Delaunay Mosaics

Given a locally finite set $A\subseteq R^d$ and a coloring $\chi :A\to \{0,1,\dots ,s\}$ , we introduce the chromatic Delaunay mosaic of $\chi$ , which is a Delaunay mosaic in $R^{d+s}$ that represents how points of different colors mingle. Our main results are bounds on the size of the chromatic Delaunay mosaic, in which we assume that d and s are constants. For example, if A is finite with $n=\#A$ , and the coloring is random, then the chromatic Delaunay mosaic has $O\left(n^{\lceil d/2\rceil }\right)$ cells in expectation. In contrast, for Delone sets and Poisson point processes in $R^d$ , the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in $R^2$ all colorings of a well spread set of n points have chromatic Delaunay mosaics of size O(n). This encourages the use of chromatic Delaunay mosaics in applications.