Center for Algorithms and Theory of Computation

CS 269S, Fall 2018: Theory Seminar
Bren Hall, Room 1423, 1pm


December 7, 2018:

Client Cover and Nearest Neighbors

Daniel Frishberg

Alt et al. show an $O((n+m)\log m)$ algorithm for covering $n$ fixed collinear points with $m$ fixed-center disks (in line with the points), at a $2$-approximation of minimal sum of disk radii. The algorithm presented here achieves the same approximation in $O(n+m)$ time, assuming the input is sorted and distances are distinct.

(Joint work with Nil Mamano and Pedro Matias)