Given a set $S$ and some symmetric distance function $d(i, j)$ defined over the elements of $S$, we must maintain the closest pair of elements (i.e., $(c_1, c_2) \mid d(c_1, c_2) \leq d(i, j) \forall i,j \in S$) subject to insertions and deletions to $S$. Further, we can assume that the possible elements to be inserted belong to a known, enumerable set $X$.
A trivial algorithm requires $O(|S|)$ for insertions (we check the distance from the newly-inserted element to any other element), and $O(|S|^2)$ for deletions (if we are removing either $c_1$ or $c_2$, we must recompute it by evaluating all pairs; although one can say this is $O(|S|)$ amortized over all possible deletions, in my application the deleted element is usually $c_1$ or $c_2$).
Has this problem been studied in the literature? Can we do better, considering available memory is of the order of $|X|^2$?