  We revisit a classical problem in computational geometry: finding the
largest-volume axis-aligned empty box (inside a given bounding box) amidst $n$
given points in $d$ dimensions. Previously, the best algorithms known have
running time $O(n\log^2n)$ for $d=2$ (by Aggarwal and Suri [SoCG'87]) and near
$n^d$ for $d\ge 3$. We describe faster algorithms with running time (i)
$O(n2^{O(\log^*n)}\log n)$ for $d=2$, (ii) $O(n^{2.5+o(1)})$ time for $d=3$,
and (iii) $\widetilde{O}(n^{(5d+2)/6})$ time for any constant $d\ge 4$.
  To obtain the higher-dimensional result, we adapt and extend previous
techniques for Klee's measure problem to optimize certain objective functions
over the complement of a union of orthants.
