June 11, 2021, 1:00 – 1:50:
Faster Core-Set Constructions and Data-Stream Algorithms in Fixed Dimensions
Martha Osegueda
We speed up previous -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
. These results are obtained using the core-set framework
proposed by Agarwal, Har-Peled, and Varadarajan.
(Based on a
paper by Timothy M. Chan.)