A step in the Delaunay mosaic of order \(k\) (Q2035135)

The main object of study in this paper is the order-\(k\) Delaunay mosaic, denoted \(\textrm{Del}_k(X)\), of a locally finite subset \(X\) of \(\mathbb{R}^d\). Constructed in [\textit{F. Aurenhammer}, Discrete Comput. Geom. 5, No. 3, 243--254 (1990; Zbl 0693.68023)], this is the natural dual of the order-\(k\) Voronoi tessellation determined by \(X\), which in turn is the decomposition of \(\mathbb{R}^d\) into closed convex domains so that each domain is the set of points closest to a fixed \(k\)-element subset of \(X\). Being the dual of this, one can think of cells in \(\textrm{Del}_k(X)\) as representing collections of intersecting domains. There is a natural function \(\textbf{w}_k \colon \textrm{Del}_k(X) \to \mathbb{R}\) given by sending a cell to the minimum \(r\) such that the corresponding intersection of domains contains some ``witness'' point within distance \(r\) of each of the \(k\) nearest neighbors in \(X\). This function is not a (Forman-style) discrete Morse function, nor a so called generalized discrete Morse function, but the main result of the present paper is that it nonetheless behaves similarly to a discrete Morse function in certain ways. More precisely (see Section~3), the authors establish a classification of how the topology of the sublevels changes at both critical and non-critical steps.