Minimum-Width Double-Slabs and Widest Empty Slabs in High Dimensions

A slab in d-dimensional space \(\mathbb {R}^d\) is the set of points enclosed by two parallel hyperplanes. We consider the problem of finding an optimal pair of parallel slabs, called a double-slab, that covers a given set P of n points in  \(\mathbb {R}^d\) . We address two optimization problems in  \(\mathbb {R}^d\) for any fixed dimension  \(d\geqslant 3\) : the minimum-width double-slab problem, in which one wants to minimize the maximum width of the two slabs of the resulting double-slab, and the widest empty slab problem, in which one wants to maximize the gap between the two slabs. Our results include the first nontrivial exact algorithms that solve the former problem for  \(d\geqslant 3\) and the latter problem for  \(d\geqslant 4\) .