Randomized algorithm estimates mixed volumes of convex shapes efficiently
Exposition of an approximation algorithm for mixed volumes of a constant number of convex bodies
Computational Geometry
Summary
Calculating the mixed volumes of several multi-dimensional shapes is a complex math problem important in geometry and optimization. The authors present a randomized method that approximates these volumes accurately and quickly when dealing with a fixed number of shapes. This method relies on being able to check if points lie inside the shapes and works efficiently when the number of shapes is fixed, regardless of dimension size. The algorithm guarantees results close to the true volume with high confidence using a reasonable amount of computation.
What this means in practice
- •For computer graphics engineers: Estimate combined volumes in high-dimensional shape modeling to improve rendering and collision detection.
- •For optimization software developers: Incorporate efficient volume estimation of convex sets into optimization algorithms that handle uncertainty and constraints.
Authors
Hariharan Narayanan
Abstract
We study $\varepsilon$-relative approximation of mixed volumes of a fixed number $k$ of full-dimensional convex bodies in $\mathbb{R}^n$, given membership oracles and a known bound $B_n\subseteq K_i\subseteq R_0B_n$. We present a randomized algorithm that estimates any prescribed mixed volume within relative error $\varepsilon$ with probability at least $1-δ$, using polynomially many oracle calls and bit operations in $n$, $\log R_0$, $\varepsilon^{-1}$, and $\logδ^{-1}$ for fixed $k$.