Dynamic and Streaming Algorithms for Union Volume Estimation

Sujoy Bhore, Karl Bringmann, Timothy M. Chan +1

The union volume estimation problem asks to $(1\pm \epsilon )$-approximate the volume of the union of $n$ given objects $X_1,\dots ,X_n\subset {\mathbb{R}}^d$. In their seminal wor…