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 $\text{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+\epsilon)$-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 \text{poly}(\epsilon^{-1}, \log n)$, improving upon the amortized update time of $k^6 d \cdot \text{poly}(\epsilon^{-1}, \log n)$ by Biabani et al. [NeurIPS'24].

翻译：本文研究了动态点集$P \\subset \\mathbb{R}^d$的直径维护与$k$-中心聚类这两个基础问题，其中点可能随时间插入或删除，且环境维度$d$非常量并可能很高。我们的研究重点在于设计即使在自适应对抗环境下仍保持有效的算法——这种对抗方在任意时刻$t$都能掌握算法输出的完整历史记录以及截至该时刻算法使用的所有随机比特。我们提出了一种完全动态算法，能以最坏情况更新时间为$\\text{poly}(d, \\log n)$维护$2$-近似直径（其中$n$为数据流长度）。该成果通过识别出仅需低频更新的鲁棒数据集代表元，并结合精细的去摊销化技术实现。据我们所知，这是首个在高维直径问题中同时实现$2$-近似保证且能抵御自适应对抗的高效完全动态算法。我们还提出了一种改进的动态$(4+\\epsilon)$-近似$k$-中心聚类算法，同样具备对抗自适应攻击的鲁棒性。该聚类算法实现了$k^{2.5} d \\cdot \\text{poly}(\\epsilon^{-1}, \\log n)$的摊销更新时间，较Biabani等人[NeurIPS'24]提出的$k^6 d \\cdot \\text{poly}(\\epsilon^{-1}, \\log n)$有所提升。