Faster Query Times for Fully Dynamic k-Center Clustering with Outliers

Given a point set P ⊆ M from a metric space (M, d) and numbers k, z ∈ N, the metric k-center problem with z outliers is to find a set C * ⊆ P of k points such that the maximum distance of all but at most z outlier points of P to their nearest center in C * is minimized. We consider this problem in the fully dynamic model, i.e., under insertions and deletions of points, for the case that the metric space has a bounded doubling dimension dim. We utilize a hierarchical data structure to maintain the points and their neighborhoods, which enables us to efficiently find the clusters. In particular, our data structure can be queried at any time to generate a (3 + ε)-approximate solution for input values of k and z in worst-case query time ε -O(dim) k log n log log ∆, where ∆ is the ratio between the maximum and minimum distance between two points in P . Moreover, it allows insertion/deletion of a point in worst-case update time ε -O(dim) log n log ∆. Our result achieves a significantly faster query time with respect to k and z than the current state-of-theart by Pellizzoni, Pietracaprina, and Pucci [18], which uses ε -O(dim) (k + z) 2 log ∆ query time to obtain a (3 + ε)-approximate solution.