We speed up previous \((1+\varepsilon)\)-factor approximation algorithms for a number of geometric optimization problems in fixed dimensions: diameter, width, minimum-radius enclosing cylinder, minimum-width enclosing annulus, minimum-width enclosing cylindrical shell, etc. Linear time bounds were known before; we further improve the dependence of the “constants” in terms of \(\varepsilon\). These results are obtained using the core-set framework proposed by Agarwal, Har-Peled, and Varadarajan.
(Based on a paper by Timothy M. Chan.)