CS Paper Radar

Estimating the Volume of a Union of Convex Bodies

Eeshan Banerjee, Aranya Kumar Bal, Debabrota Basu, Sourav Chakraborty, Debarshi Chanda, Uddalok Sarkar

cs.DS ·submitted 2026-11-04 11:26 UTC · v1

Abstract

The \textit{Union Volume Estimation problem}, i.e. yielding an $(\varepsilon, δ)$-approximation of the volume of the union of convex bodies, is a classical problem in computational geometry and formal methods. In this paper, we first detect where and why the efficient union volume estimators with approximate sampling and PAC volume estimation oracles fail. Specifically, we show that having only TV-distance guarantees on the approximate sampler does not suffice, and demonstrate this bottleneck by constructing the sunflower families of convex bodies. In this context, we propose the concept of \textit{tail-controlled samplers} that can yield with high-probability almost-$\ell_{\infty}$ closeness. Secondly, we leverage this concept to propose a generic algorithmic framework \texttt{Alpona} that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an $(\varepsilon, δ)$-estimate of the union volume for any collection of convex bodies. We show that \texttt{Alpona} needs only linear (in number of convex bodies) oracle calls to be $(\varepsilon, δ)$-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler~\citep{lovasz2006fast}. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate \texttt{Alpona}'s correctness for the sparse frequency streams of convex bodies: a special case of the union volume estimation problem where no convex body intersects more than $τ$ many other bodies.

Closest papers

Nearest neighbours by meaning across the whole index.

A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

cs.DS cs.LGmath.FAmath.OC ·2026-09-24 ·Santosh S. Vempala
theory similarity 0.74
Abstract · toc, figures, fewer logs

We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling, this improves on the previous linear lower bound. Our construction also implies the same lower bound for volume estimation.

0.54

An $\mathsf{FPRAS}$ for Mixed Volumes

cs.DS cs.CCcs.CGmath.CO+1 ·2026-11-01 ·Xiaoyu Chen, Kuikui Liu
similarity 0.71
Abstract

We design the first fully polynomial-time randomized approximation scheme ($\mathsf{FPRAS}$) to estimate the mixed volume of $n$ arbitrary compact convex sets in $\mathbb{R}^{n}$ specified by weak membership oracles. This disproves a longstanding conjecture of Gurvits (2009). $\textbf{AI Disclosure}$ The main ideas were generated entirely by GPT 6 Astra. The purpose of this paper is to provide a human-written exposition of the algorithm.

0.12

Approximation algorithm for mixed volumes of a constant number of convex bodies

cs.CG math.MG ·2026-10-06 ·Hariharan Narayanan
similarity 0.69
Abstract · 42 pages

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 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.

0.45

Near-Optimal Oracle Bounds for Isotropic Rounding

cs.DS ·2026-10-05 ·Yang P. Liu, Richard Peng, Alicia Stepin, Colin Tang
theoryhighly cited similarity 0.64
Abstract

We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower bound, even when $R/r=n^{O(1)}$. The key lemma states that if $B(0,1)\subseteq K$ and $\Cov(\Unif(K))\preceqκI_n$, with $κ\ge1$, then approximate uniform sampling from an initial density bounded by a constant times the uniform density uses $\Ot(n^2\sqrtκ)$ expected membership queries. We prove this by simulating reflected kinetic dynamics using the analysis of Eberle and Lörler~\cite{EL26:journal}. Combining this sampler with the ideas of Jia, Laddha, Lee, and Vempala~\cite{JLLV26:journal} for rounding well-rounded bodies yields our $\Ot(n^3)$ query rounding algorithm. We also give a counterexample to an ellipsoid-growth conjecture from previous papers on this topic.

0.50

Fundamental Limits of Sampling-Based Reachability: Geometry and Flow Distortion

eess.SY cs.RO ·2026-10-29 ·Jixian Liu, Ihab Tabbara, Hussein Sibai, Enrique Mallada
theorycode/data similarity 0.61
Abstract · 16 pages, 9 figures, 3 tables. Extended version of the CoRL 2026 paper; submitted to IEEE Transactions on Automatic Control. Code: https://g…

Sampling-based reachability estimates reachable sets from finitely many simulated trajectory endpoints. Existing guarantees often control missed probability mass or approximation error relative to the convex hull of the reachable set, leaving the geometric error relative to the reachable set incompletely characterized. We study this error as a problem of support estimation under flow distortion. Our assumptions combine a uniform lower bound on the local volume density of the initial set, a lower bound on the sampling density, and a one-sided Lipschitz constant $μ$ for the vector field. These conditions admit initial sets with corners and dynamics that may expand or contract. In the fine-accuracy regime, $\tilde{\mathcal O}\bigl(2^ne^{nμT}(R/r)^n/(ρκ)\bigr)$ independent endpoint samples suffice for Hausdorff accuracy $r$ using the endpoint cloud. Here, $n$ is the state dimension, $T$ is the horizon, $R$ is the volume-equivalent radius, and $ρ$ and $κ$ quantify sampling density and local volume density. For $n\ge2$ and sufficiently small $κ$, a minimax lower bound over all estimators based only on independent endpoints matches these dependencies up to a dimension-dependent factor $2\cdot4^n$ and logarithmic factors, within the stated parameter range and when the state domain accommodates the construction. The exponential burden in dimension, and in the horizon for expanding systems, is therefore intrinsic to this observation model. Planar experiments illustrate the predicted effects of corners and contraction; robot-arm experiments show how empirical accuracy deteriorates with dimension.

0.49

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

cs.CC stat.MLcs.LGmath.ST ·2026-11-02 ·Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao +1 more
theory similarity 0.55
Abstract

We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

0.17

Polytope Sampling at the Speed of Isoperimetry

cs.DS math.OCmath.PR ·2026-10-16 ·Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang
similarity 0.55
Abstract · 58 pages

We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \cdot \mathrm{poly}\log(\frac m δ)$ iterations, each running in time $O(mn^{ω- 1})$, to return a sample within total variation distance $δ$ to the uniform distribution. When $m =O(n)$ and $δ= \mathrm{poly}(\frac 1 n)$, our runtime improves upon all prior works by an $Ω(n^{2/3})$ factor. Our sampler is based on the recent \emph{functional stochastic localization} framework of [GST26], and achieves an iteration count nearly matching the Poincaré constant of the uniform distribution with respect to the logarithmic barrier.

0.55

Optimal random quantisers for spherically symmetric distributions

cs.LG math.STstat.ML ·2026-10-08 ·Luc Pronzato, Anatoly Zhigljavsky
theory similarity 0.54
Abstract

Zador's celebrated theorem is a cornerstone of optimal quantisation: it establishes both the weak limit of the empirical distribution of an optimal $n$-point quantiser in $R^d$ and the decay rate of the associated $L_s$-mean quantisation error. In large dimension, however, observing this asymptotic behaviour requires an astronomically large sample size. We prove that, for spherically symmetric target distributions, optimisation over all spherically symmetric distributions is a convex problem and derive an equivalence theorem that both characterises global optimality and yields a constructive algorithm. We show that, for moderate $n$, random quantisers uniformly distributed on a sphere of suitably chosen radius $R$ perform exceptionally well and, over a broad range of values of $n$, are numerically certified to be optimal among all random quantisers. Their expected distortion has an explicit integral representation that can be evaluated to arbitrary precision, and we prove concentration across random quantisers: the distortion variance tends to zero as $n\to\infty$ for fixed $d$. For $s=2$, both the optimal radius and the associated minimum expected distortion admit exact expressions. For general $s$, the optimal radius can be determined efficiently, and extreme-value theory provides useful approximations when $n$ grows with $d$. Depending on this growth rate, $R$ either converges to zero or approaches a positive limit that is independent of $s$.

0.57