CODEWITHSUNDEEP
algorithmcoordinatesdistance
Abhinav Garg
Abhinav Garg

Reputation: 1692

how to find out of two points which one is closest to a set of points?

how to find out of two points which one is closest to a set of points?

Suppose I have two points (x1,y1) and (x2,y2), I want to know which one is closer to a Set of points p1, p2, p3, p4.

Is there any algorithm for this??

Number of input points and the number of points in the Set are not fixed

We can have n number of inputs as well as n number of points in Set.

Upvotes: 1

Views: 155

Answers (2)

Walter Tross
Walter Tross

Reputation: 12625

It all depends on how you define being “closest to a set of points”.

One super fast criterion could be “having the minimum sum of square distances to a set of points” (square distances are used, e.g., in curve fitting, so nothing strange here).

Using this criterion, you would just have to minimize Σᵢ((xᵢ-x)²+(yᵢ-y)²) , where i is the index over the set.

Upvotes: 1

user1196549
user1196549

Reputation:

Construct a kD-tree on the Set points. This can be done in time Ns Log Ns.

Then for every Input point, find the nearest neighbor. This takes Ni Log Ns time. And finally, find the shortest distance in Ni comparisons.

Total time, (Ns + Ni) Log Ns. This is to be compared to brute force, taking Ns.Ni. For small Ni, brute force is preferable.

Upvotes: 1

Related Questions