A step in the Delaunay mosaic of order k

• DOI: 10.1007/s00022-021-00577-4
• Publication Date: 2021-03-16T19:02:26Z
• Authors: Herbert Edelsbrunner; Anton Nikitenko; Georg Osang
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; Article

AbstractGiven a locally finite set $$X \subseteq {{\mathbb {R}}}^d$$

X ⊆

R

d

and an integer $$k \ge 0$$

k ≥ 0

, we consider the function $${\mathbf{w}_{k}^{}} :{\mathrm{Del}_{k}{({X})}} \rightarrow {{\mathbb {R}}}$$

w

k

:

Del k

( X )

→ R

on the dual of the order-k Voronoi tessellation, whose sublevel sets generalize the notion of alpha shapes from order-1 to order-k (Edelsbrunner et al. in IEEE Trans Inf Theory IT-29:551–559, 1983; Krasnoshchekov and Polishchuk in Inf Process Lett 114:76–83, 2014). While this function is not necessarily generalized discrete Morse, in the sense of Forman (Adv Math 134:90–145, 1998) and Freij (Discrete Math 309:3821–3829, 2009), we prove that it satisfies similar properties so that its increments can be meaningfully classified into critical and non-critical steps. This result extends to the case of weighted points and sheds light on k-fold covers with balls in Euclidean space.