Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond

In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P\subset {\mathbb{R}}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary—an adversary that, at any time $t$, knows the entire history of the algorithm’s outputs as well as all the random bits used by the algorithm up to that point.

We present a fully dynamic algorithm that maintains a $2$-approximate diameter with a worst-case update time of $poly(d,\log n)$, where $n$ is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a $2$-approximation guarantee and robustness against an adaptive adversary.

We also give an improved dynamic $(4+ϵ)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5}d\cdot poly({ϵ}^{-1},\log n)$, improving upon the amortized update time of $k^{6}d\cdot poly({ϵ}^{-1},\log n)$ by Biabani et al. NeurIPS'24.