2025/08/27 by Narayanan, Hariharan, Roy, Sourav
#52A39 #68Q25 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.19582
We study the problem of approximating the mixed volume V(P1(α1), …, Pk(αk)) of an k-tuple of convex polytopes (P1, …, Pk), each of which is defined as the convex hull of at most m0 points in ℤn. We design an algorithm that produces an estimate that is within a multiplicative 1 ± ε factor of the true mixed volume with a probability greater than 1 - δ. Let the constant ∏i=2k \frac(αi+1)^αi+1αi^ αi be denoted by A. When each Pi ⊆ B_∞(2L), we show in this paper that the time complexity of the algorithm is bounded above by a polynomial in n, m0, L, A, ε-1 and log δ-1. In fact, a stronger result is proved in this paper, with slightly more involved terminology. In particular, we provide the first randomized polynomial time algorithm for computing mixed volumes of such polytopes when k is an absolute constant, but α1, …, αk are arbitrary. Our approach synthesizes tools from convex optimization, the theory of Lorentzian polynomials, and polytope subdivision.