Semi-interlaced polytopes

The Minkowski mixed volume of $n$ subpolytopes $D_1,\dots ,D_n$ of a polytope $P\subset {\mathbb{R}}^n$ clearly does not exceed the normalized volume $n!\text{Vol}(P)$. Equality holds if and only if the subpolytopes are interlaced, i.e., each proper face $F⊊P$ intersects at least $\dim (F)+1$ of the polytopes $D_i$. Efficiently computing mixed volumes for more general collections of subpolytopes is crucial for estimating the complexity of numerically solving polynomial systems. Motivated by relaxing the bound $\dim (F)+1$ to $\dim (F)$, we prove a combinatorial formula for the mixed volume of a broad class of semi-interlaced polytopes. This class includes, in particular, the off-coordinate polytopes used in computing algebraic degrees – such as Maximum Likelihood, Euclidean Distance, and Polar degrees – via the Kouchnirenko–Bernshtein theory. We also present applications of our results to the Arnold monotonicity problem (1982-16), which concerns the dependence of Milnor numbers on the Newton polyhedra.