Computing a Minimum-Width Cubic and Hypercubic Shell

In this paper, we study the problem of computing a minimum-width axis-aligned cubic shell that encloses a given set of $n$ points in a three-dimensional space. A cubic shell is a closed volume between two concentric and face-parallel cubes. Prior to this work, there was no known algorithm for this problem in the literature. We present the first nontrivial algorithm whose running time is $O(n log^2 n)$. Our approach easily extends to higher dimension, resulting in an $O(n^{lfloor d/2 rfloor} log^{d-1} n)$-time algorithm for the hypercubic shell problem in $dgeq 3$ dimension.