A heuristic for finding the vector that is maximally distant from a set of vectors

Question

I have two sets of vectors: A and B. I want to find the vector Bi in set B that is maximally distant from the vectors in set A, either by average distance or closest distance. I know that I can accomplish this by comparing every vector Ai in A with every vector Bi in B, but that will be very costly. It is acceptable for the solution to be approximate. Is there a heuristic algorithm that can solve this problem more efficiently?

Answer 1

Just to answer with some ideas.

If you have too many dimensions, you can use the Johnson–Lindenstrauss lemma to reduce the dimensions while keeping distances approximately the same (some $\epsilon$ away from original distances).

You can find a 3-approximation for the point in $B$ that is farthest away from any point in $A$ (pick any $b' \in B$, then find an $a \in A$ that is farthest away from $b'$, and then pick a $b \in B$ that is farthest away from $a$). This should be a 3-approximation for the farthest $A$-$B$-points.

However, you want to minimize the point in $B$ farthest away from all of $A$, so maybe you can try to find the centroid $c(A)$ and find the point in $B$ that is farthest away from $c(A)$? Note that this only works if most points in $A$ are close to $c(A)$. You can also try to remove outliers first.

A randomized approach could be to choose e.g. a constant fraction of the points in $A$ and perform the centroid algorithm, and repeat as many times as you see fit. Or you can choose, say $\log |A|$ many points in $A$ and find the point in $B$ farthest away from this set. Repeat as many times as you can.

These are all suggestions where we don't know anything about $A$ and $B$. How are they generated? Do they follow some probability distribution? If you use the knowledge you have about these sets, you will very likely get better algorithms.

Finally, you can see if you can use a $k$-d tree to come up with a better algorithm.