CODEWITHSUNDEEP
algorithmcomputational-geometry
user695652
user695652

Reputation: 4275

Given two point sets A and B, how do you find the point in A farthest away from B?

Does anybody know of an efficient algorithm which solves the following problem:

Given two disjoint point sets A, B of some metric space, find a point in A which maximizes the minimum distance to the closest point in B?

Upvotes: 2

Views: 242

Answers (3)

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

This is a variant on a nearest neighbor search; if you use a k-d tree to index B then a brute-force search through A would have an average runtime of n * log(m), where n is the number of points in A and m is the number of points in B. If you cluster your points in A and test the clusters' centroids then you should be able to eliminate multiple points with one query.

Upvotes: 1

Joel
Joel

Reputation: 5674

I suspect that given a metric f, you could use 1/f as a metric, then do a straightforward nearest neighbor search. The only hangup I've got is whether 1/f satisfies the triangle inequality.

Upvotes: 0

rivimey
rivimey

Reputation: 931

I don't know of a particular algorithm. Given the problem I would start off attempting to see whether a binary chop could do the job.

To make progress needs more info though: you say "point A .. from B" as if B was a point, but B is a set of points - and indeed from the problem definition A and B could be the same set of points, or at least overlap..

In attempting to find a solution, recursion can be a help, too. That is, find a solution to f(n) given a solution to f(n-1). By definition, if A is 1 point and B is too, then there is 1 known answer.

Can you then generalise a solution for n = 2

For example, solve if A is 2 points, B is one point. which A is further from B.

Once you have a solution where B is 1 point, you may be able to infer solutions for B = a set.

HTH

Upvotes: 0

Related Questions