JAVA 2D Find the K closest points to the origin in 2D plane

Question

Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large.

This is what i have so far:

   public class OriginQuestion {

     public static class Point {

     public double x;

    public double y;

 } 
  public static Point[] closestk( Point  myList[], int k ) {}
    for(int i=0;i<myList.length;i++){

    }

  }

Help appreciated

Answer 1

This problem is a variant of the nearest neighbor search problem. The simplest solution is to compute the distance from the origin to all N points and then find the K that are nearest using for example the quickselect algorithm, giving a time and space complexity of O(n).

Answer 2

This problem can be solved using heap. We can start with creating a max-heap of size k and start adding points to it. After we are done adding K points to our heap.

Now if the (K+1)th point is at distance lower than the max-heap root , we remove root and add this (K+1)th point to our max-heap.

After we are done processing all the N points, our heap will give us the solution. The worst case complexity should be N(log K) as we will do it for N numbers and log K operations are required to move a node in the heap.