CODEWITHSUNDEEP
algorithmdata-structuresgeometrynearest-neighbor
bazzi
bazzi

Reputation: 579

Given n points in a 2-D plane we have to find k nearest neighbours of each point among themselves

I explored the method using a min-heap. For each point we can store a min heap of size k but it takes too much space for large n(I m targeting for n around a 100 million). Surely there must be a better way of doing this utilising lesser space and not affecting time complexity that much. Is there some other data structure?

Upvotes: 3

Views: 553

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70931

This problem is typical setup for KD-tree. Such solution would have linearithmic complexity but may be relatively complex to implement(if a ready implementation is not available)

An alternative approach could be using bucketing to reduce the complexity of the naive algorithm. The idea is to separate the plane into "buckets" i.e. squares of some size and place the points in the bucket they belong to. The closest points will be from the closest buckets. In case of random data this could be quite good improvement but the worst case is still the same as the naive approach.

Upvotes: 4

Related Questions