Fully Dynamic <i>k</i>-Center in Low Dimensions via Approximate Furthest Neighbors

Given a set of points P, the k-center problem is to find a minimum radius r* and associated center set of k points C such that the distance from each point in P to its closest center is at most r*. While this problem is NP-hard to solve, there exists a famous O(kn) time 2-approximation algorithm due to Gonzalez. This works by repeatedly adding the furthest neighbor in P to the current center set C until C contains exactly k centers.