Estimating the Volume of a Union of Convex Bodies
Abstract
The Union Volume Estimation problem, i.e. yielding an (ε, δ)-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 tail-controlled samplers that can yield with high-probability almost-ℓ∞ closeness. Secondly, we leverage this concept to propose a generic algorithmic framework Alpona that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an (ε, δ)-estimate of the union volume for any collection of convex bodies. We show that Alpona needs only linear (in number of convex bodies) oracle calls to be (ε, δ)-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler [Lovász and Vempala, 2006]. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate 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.
Related
- Maximal volume of convex bodies avoiding random points and lacunary dilates
- The Petty Conjecture for Convex Bodies of Revolution
- Riemannian convex bodies with a geodesic segment on the boundary
- Continuity and monotonicity of weighted perimeters of convex bodies
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
BibTeX
@misc{banerjee2026estimating,
title = {{Estimating the Volume of a Union of Convex Bodies}},
author = {Eeshan Banerjee and Aranya Kumar Bal and Debabrota Basu and Sourav Chakraborty and Debarshi Chanda and Uddalok Sarkar},
howpublished = {HAL},
year = {2026},
month = nov,
eprint = {2611.06364},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05855047v1},
note = {CC BY-NC 4.0},
}
RIS
TY - UNPB
TI - Estimating the Volume of a Union of Convex Bodies
AU - Eeshan Banerjee
AU - Aranya Kumar Bal
AU - Debabrota Basu
AU - Sourav Chakraborty
AU - Debarshi Chanda
AU - Uddalok Sarkar
PY - 2026
DA - 2026/11/04
PB - HAL
UR - https://hal.science/hal-05855047v1
AB - The Union Volume Estimation problem, i.e. yielding an (ε, δ)-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 tail-controlled samplers that can yield with high-probability almost-ℓ_∞ closeness. Secondly, we leverage this concept to propose a generic algorithmic framework Alpona that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an (ε, δ)-estimate of the union volume for any collection of convex bodies. We show that Alpona needs only linear (in number of convex bodies) oracle calls to be (ε, δ)-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler [Lovász and Vempala, 2006]. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate 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.
ER -