An easy still unsolved special case of Klee's measure problem with applications in multiple objective optimization is described in the following.
Let $[\vec a_1,\vec b_1],\dots,[\vec a_n,\vec b_n]$ denote $n$ interval boxes in $\mathbb R^d$. Then the Klee measure problem is to compute efficiently the $d$-dimensional Lebesgue measure of the union $\bigcup_{i=1}^n[\vec a_i,\vec b_i]$.
The specialized problem for anchored boxes is adding the condition $\vec a=\vec a_1=\dots=\vec a_n$. Computing the Lebesgue measure of the union of anchored boxes is known as the ``hypervolume indicator'' problem (HVI problem).
For $d=2$ and $d=3$ asymptotically efficient algorithms with time complexity $\Theta(n \log n)$ are known. For $d\ge 4$ the combinatorial complexity (the number of boxes into which the polytope $\bigcup_{i=1}^n[\vec a_i,\vec b_i]$ can be partitioned) was analyzed by Lacour, Klamroth, Fonseca. Surprisingly, it exceeds the time complexity of best known algorithms for computing HVI in $d\ge 4$ dimensions, in terms of asymptotic time complexity. The best known algorithm for $d\ge 4$ has been proposed by Timothey Chan in 2013. It has complexity $O(n^{d/3}\mathrm{polylog}(n))$.
Does there exists a smaller bound, i.e., a faster algorithm?
Remark. The lower bound for time complexity is $\Omega(n\log n)$.
The problem was posed on June 5, 2019 by Michael Emmerich from leider University on page 122 of Volume 2 of the Lviv Scottish Book.
Prize: 4-D Rubik's cube.
