Fully dynamic hierarchical diameter k-clustering and k-center

Abstract

We develop dynamic data structures for maintaining a hierarchical k-center clustering when the points come from a discrete space $\{1,\dots ,\Delta {\}}^d$. Our first data structure is for the low dimensional setting, i.e., d is a constant, and processes insertions, deletions and cluster representative queries in ${\log }^{O(1)}(\Delta n)$ time, where $n$ is the current size of the point set. For the high dimensional case and an integer parameter $\ell >1$, we provide a randomized data structure that maintains an $O(d\ell )$-approximation. The amortized expected insertion time is $O(d^2\ell \log n\log \Delta )$. The amortized expected deletion time is $O(d^2{n}^{1/\ell }{\log }^{2}n\log \Delta )$. At any point of time, with probability at least $1-1/n$, the data structure can correctly answer all queries for cluster representatives in $O(d\ell \log n\log \Delta )$ time per query.