Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation

Karl Bringmann, Kasper Green Larsen, André Nusser +2

Union volume estimation is a classical algorithmic problem. Given a family of objects $O_1,\dots ,O_n\subseteq {\mathbb{R}}^d$, we want to approximate the volume of their union. In…