3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Another related question. $\endgroup$ Oct 9 at 18:53
  • $\begingroup$ @PålGD The dimension-space is potentially unlimited. O(nlogn) would be acceptable. $\endgroup$
    – magnetlion
    Oct 9 at 20:07
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.