Computing the width of a point set in 3-space.
Bernd Gärtner, Thomas Herrmann · 2001
We present a new algorithm to solve the 3-dimensional width problem, i.e. to determine two parallel planes of smallest distance such that the region between the two planes contains a given point set. Like the algorithm of Houle and Toussaint, our method has quadratic worstcase complexity but is much faster in practice. In contrast to Houle and Toussaint, we do not use plane sweep or point location techniques; instead, we apply simple methods from linear optimization. The resulting implementation seems to be faster than an existing implementation of Houle and Toussaint's method using the Leda library, and it is now part of the Computational Geometry Algorithms Library Cgal.