1
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ How is the distance function specified? What space are the elements of $S$ taken from? In other words, what is $X$? Is $X$ the set of real numbers? Integers? Something else? Different choices of distance function and of $X$ will probably lead to different answers, and it's probably too much to expect someone to exhaustively cover all possibilities, so I think you need to tell us which one is applicable in your situation. $\endgroup$ – D.W. Nov 24 '17 at 5:10
  • $\begingroup$ The distance function can be seen as a deterministic black box. It can have different semantics depending on the problem instance. The elements of $S$ or $X$ are also not in any specific domain, but may as well be labelled with integers $X=\{1,\ldots,n\}$ and $S\subseteq X$. I'm not looking for an exhaustive list for each possible case, but rather whether there is some method that solves the generic problem for an arbitrary distance function. $\endgroup$ – LLLL Nov 24 '17 at 23:28
  • $\begingroup$ Are you sure you don't know anything about the distance function? If we don't know anything about the structure of the black box, then the problem is uninteresting: the naive algorithms runs in $O(|S|^2)$ time, and I think one can use an adversary argument to show that no algorithm can run faster (if there is any pair of elements $(c_i,c_j)$ that we haven't queried the black box with, then your answer might be wrong: for all we know the distance between them might be tiny, or it might be huge). $\endgroup$ – D.W. Nov 25 '17 at 4:14
  • $\begingroup$ Rather than trying to find a single algorithm that works for all distance functions (generically), I suggest that you pick a specific universe $X$ and a specific distance function and focus on algorithms for that particular setting. $\endgroup$ – D.W. Nov 25 '17 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.