  The order-$k$ Voronoi tessellation of a locally finite set $X \subseteq
\mathbb{R}^n$ decomposes $\mathbb{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.
