Center for Algorithms and Theory of Computation

CS 269S, Spring 2021: Theory Seminar


June 11, 2021, 1:00 – 1:50:

Faster Core-Set Constructions and Data-Stream Algorithms in Fixed Dimensions

Martha Osegueda

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.)