{"id":"arxiv/2610.08248","url":"https://arxiv.org/abs/2610.08248","tags":["cs.CG","math.MG"],"score":0,"title":"Approximation algorithm for mixed volumes of a constant number of convex bodies","domain":"cs.CG","source":"arxiv","authors":["Hariharan Narayanan"],"reviews":0,"subject":"cs.CG","summary":"We study the computation of mixed volumes of convex sets given as rational subspace sections of bodies described by membership oracles. The sets need not have nonempty interior. For positive multiplicities $α_1+\\cdots+α_k=n$, we give a randomized algorithm that computes a relative $\\varepsilon$-approximation with probability at least $1-δ$. Its running time is polynomial in Gurvits' factor $Γ_α=(n^n/n!)\\prod_iα_i!/α_i^{α_i}$, the input presentation length, and $\\varepsilon^{-1}$, and linear in $1+\\logδ^{-1}$, with degree independent of $k$. The running-time bound holds for every choice of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}