Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions $d\ge 4$

Egor Gorbachev, Marvin Künnemann

Klee's measure problem (computing the volume of the union of $n$ axis-parallel boxes in ${\mathbb{R}}^d$) is well known to have $n^{\frac{d}{2}\pm o(1)}$-time algorithms (Overmars, Y…