Approximating mixed volumes to arbitrary accuracy
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918264304566272 |
|---|---|
| author | Narayanan, Hariharan Roy, Sourav |
| author_facet | Narayanan, Hariharan Roy, Sourav |
| contents | We study the problem of approximating the mixed volume $V(P_1^{(α_1)}, \dots, P_k^{(α_k)})$ of an $k$-tuple of convex polytopes $(P_1, \dots, P_k)$, each of which is defined as the convex hull of at most $m_0$ points in $\mathbb{Z}^n$. We design an algorithm that produces an estimate that is within a multiplicative $1 \pm ε$ factor of the true mixed volume with a probability greater than $1 - δ.$ Let the constant $ \prod_{i=2}^{k} \frac{(α_{i}+1)^{α_{i}+1}}{α_{i}^{\,α_{i}}}$ be denoted by $\tilde{A}$. When each $P_i \subseteq B_\infty(2^L)$, we show in this paper that the time complexity of the algorithm is bounded above by a polynomial in $n, m_0, L, \tilde{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, \dots, α_k$ are arbitrary. Our approach synthesizes tools from convex optimization, the theory of Lorentzian polynomials, and polytope subdivision. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19582 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating mixed volumes to arbitrary accuracy Narayanan, Hariharan Roy, Sourav Computational Geometry Combinatorics 52A39, 68Q25 We study the problem of approximating the mixed volume $V(P_1^{(α_1)}, \dots, P_k^{(α_k)})$ of an $k$-tuple of convex polytopes $(P_1, \dots, P_k)$, each of which is defined as the convex hull of at most $m_0$ points in $\mathbb{Z}^n$. We design an algorithm that produces an estimate that is within a multiplicative $1 \pm ε$ factor of the true mixed volume with a probability greater than $1 - δ.$ Let the constant $ \prod_{i=2}^{k} \frac{(α_{i}+1)^{α_{i}+1}}{α_{i}^{\,α_{i}}}$ be denoted by $\tilde{A}$. When each $P_i \subseteq B_\infty(2^L)$, we show in this paper that the time complexity of the algorithm is bounded above by a polynomial in $n, m_0, L, \tilde{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, \dots, α_k$ are arbitrary. Our approach synthesizes tools from convex optimization, the theory of Lorentzian polynomials, and polytope subdivision. |
| title | Approximating mixed volumes to arbitrary accuracy |
| topic | Computational Geometry Combinatorics 52A39, 68Q25 |
| url | https://arxiv.org/abs/2508.19582 |