Abstract Given a locally finite set $$A \subseteq {{\mathbb R}}^d$$ A ⊆ R d and a coloring $$\chi :A \rightarrow \{0,1,\ldots ,s\}$$ χ : A → { 0 , 1 , … , s } , we introduce the chromatic Delaunay mosaic of $$\chi $$ χ , which is a Delaunay mosaic in $${{\mathbb R}}^{d+s}$$ 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}}$$ n = # A , and the coloring is random, then the chromatic Delaunay mosaic has $$O(n^{{\lceil d/2 \rceil }})$$ O ( n ⌈ d / 2 ⌉ ) cells in expectation. In contrast, for Delone sets and Poisson point processes in $${{\mathbb R}}^d$$ 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 $${{\mathbb R}}^2$$ 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.

We propose a characterization of discrete analytical spheres, planes and lines in the body-centered cubic (BCC) grid, both in the Cartesian and in the recently proposed alternative compact coordinate system, in which each integer triplet addresses some voxel in the grid. We define spheres and planes through double Diophantine inequalities and investigate their relevant topological features, such as functionality or the interrelation between the thickness of the objects and their connectivity and separation properties. We define lines as the intersection of planes. The number of the planes (up to six) is equal to the number of the pairs of faces of a BCC voxel that are parallel to the line.

Abstract The Voronoi tessellation in $${{{\mathbb {R}}}}^d$$ R d is defined by locally minimizing the power distance to given weighted points. Symmetrically, the Delaunay mosaic can be defined by locally maximizing the negative power distance to other such points. We prove that the average of the two piecewise quadratic functions is piecewise linear, and that all three functions have the same critical points and values. Discretizing the two piecewise quadratic functions, we get the alpha shapes as sublevel sets of the discrete function on the Delaunay mosaic, and analogous shapes as superlevel sets of the discrete function on the Voronoi tessellation. For the same non-critical value, the corresponding shapes are disjoint, separated by a narrow channel that contains no critical points but the entire level set of the piecewise linear function.