Computing a Minimum-Width Cubic and Hypercubic Shell

Abstract

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 $d\ge 3$ dimension.

13 pages, 4 figures