Search code examples
javasortingbig-oclosest-points

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

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

Solution

  • 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).