Approximation algorithm for mixed volumes of a constant number of convex bodies
Abstract
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+⋯+αk=n, we give a randomized algorithm that computes a relative ε-approximation with probability at least 1−δ. Its running time is polynomial in Gurvits' factor Γα=(nn/n!)∏iαi!/αiαi, the input presentation length, and ε−1, and linear in 1+logδ−1, with degree independent of k. The running-time bound holds for every choice of the random bits, and zero mixed volumes are detected exactly. We extend the capacity-scaling and sampling method of Narayanan--Roy by using rational projections and a smooth mixed Monge--Ampère representation. In particular, the algorithm runs in randomized polynomial time when the number of distinct convex sets is bounded above by a constant.
Related
- Expected mixed volumes of convex hulls of random walks and Lévy processes
- Sharp approximation thresholds for power means of common-subspace volumes
- Angles and volumes of simplices, boxes, and crosspolytopes in constant curvature
- Arithmetic purity of strong approximation for toric varieties with constant global sections
- Beyond Constant Truncations: The Bounded Sobolev Approximation Gap
BibTeX
@misc{narayanan2026approximation,
title = {{Approximation algorithm for mixed volumes of a constant number of convex bodies}},
author = {Hariharan Narayanan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08248},
eprint = {2610.08248},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08248},
}
RIS
TY - UNPB
TI - Approximation algorithm for mixed volumes of a constant number of convex bodies
AU - Hariharan Narayanan
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.08248
UR - https://arxiv.org/abs/2610.08248
AB - 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+⋯+α_k=n, we give a randomized algorithm that computes a relative ε-approximation with probability at least 1−δ. Its running time is polynomial in Gurvits' factor Γ_α=(n^n/n!)∏_iα_i!/α_i^α_i, the input presentation length, and ε^−1, and linear in 1+logδ^−1, with degree independent of k. The running-time bound holds for every choice of the random bits, and zero mixed volumes are detected exactly. We extend the capacity-scaling and sampling method of Narayanan--Roy by using rational projections and a smooth mixed Monge--Ampère representation. In particular, the algorithm runs in randomized polynomial time when the number of distinct convex sets is bounded above by a constant.
ER -