Approximation algorithm for mixed volumes of a constant number of convex bodies
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.08248
curl -X POST /api/v1/records/arxiv/2610.08248/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.08248/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'