Poisson-Delaunay Mosaics of Order k

Abstract

The order-k Voronoi tessellation of a locally finite set $X\subseteq R^n$ decomposes $R^n$ into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.

Keywords: Delaunay mosaics of order k; Discrete Morse theory; Poisson point process; Stochastic geometry; Voronoi tessellations of order k.

Fig. 1

The dotted edges decompose the plane into the order-1 Voronoi domains, while the solid edges decompose it into order-2 Voronoi domains. Observe that the two tessellations share some of their vertices but not all

Fig. 2

The order-1 Delaunay mosaic on the left and the order-2 Delaunay mosaic on the right, both superimposed on their corresponding Voronoi tessellations

Fig. 3

The three barycenter polytopes in ${\mathbb{R}}^3$: the generation-1 tetrahedron, the generation-2 octahedron, and the generation-3 tetrahedron

Fig. 4

The radius function partitions the order-2 Delaunay mosaic of the three points into four relaxed intervals: three contain a vertex each, and the fourth relaxed interval contains the triangle together with its three edges