@inproceedings{Bringmann_SoCG2025, TITLE = {Approximating {K}lee's Measure Problem and a Lower Bound for Union Volume Estimation}, AUTHOR = {Bringmann, Karl and Larsen, Kasper Green and Nusser, Andr{\'e} and Rotenberg, Eva and Wang, Yanheng}, LANGUAGE = {eng}, ISBN = {978-3-95977-370-6}, URL = {urn:nbn:de:0030-drops-231778}, DOI = {10.4230/LIPIcs.SoCG.2025.25}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2025}, MARGINALMARK = {$\bullet$}, DATE = {2025}, ABSTRACT = {Union volume estimation is a classical algorithmic problem. Given a family of
objects $O_1,\ldots,O_n \subseteq \mathbb{R}^d$, we want to approximate the
volume of their union. In the special case where all objects are boxes (also
known as hyperrectangles) this is known as Klee's measure problem. The
state-of-the-art algorithm [Karp, Luby, Madras '89] for union volume estimation
and Klee's measure problem in constant dimension $d$ computes a
$(1+\varepsilon)$-approximation with constant success probability by using a
total of $O(n/\varepsilon^2)$ queries of the form (i) ask for the volume of
$O_i$, (ii) sample a point uniformly at random from $O_i$, and (iii) query
whether a given point is contained in $O_i$.
We show that if one can only interact with the objects via the aforementioned
three queries, the query complexity of [Karp, Luby, Madras '89] is indeed
optimal, i.e., $\Omega(n/\varepsilon^2)$ queries are necessary. Our lower bound
already holds for estimating the union of equiponderous axis-aligned polygons
in $\mathbb{R}^2$, and even if the algorithm is allowed to inspect the
coordinates of the points sampled from the polygons, and still holds when a
containment query can ask containment of an arbitrary (not sampled) point.
Guided by the insights of the lower bound, we provide a more efficient
approximation algorithm for Klee's measure problem improving the
$O(n/\varepsilon^2)$ time to $O((n+\frac{1}{\varepsilon^2}) \cdot
\log^{O(d)}n)$. We achieve this improvement by exploiting the geometry of
Klee's measure problem in various ways: (1) Since we have access to the boxes'
coordinates, we can split the boxes into classes of boxes of similar shape. (2)
Within each class, we show how to sample from the union of all boxes, by using
orthogonal range searching. And (3) we exploit that boxes of different classes
have small intersection, for most pairs of classes.
}, BOOKTITLE = {41st International Symposium on Computational Geometry (SoCG 2025)}, EDITOR = {Aichholzer, Oswin and Wang, Haitao}, PAGES = {1--16}, EID = {25}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {332}, ADDRESS = {Kanazawa, Japan}, }