title: Find closest point of every point (Nearest Neighbor)
body: <p>I am writing a method that takes as input an array of points and finds, for each point in the array, the closest point to it other than itself. I am currently doing this in a brute force way (cheking every point with every other point). My current implimentation doesn't have the array sorted but i can sort it by p.x values with the CompareByX method. I am chekcking the running time of the algorithm, and it gets very time consuming with large values of n. I am not very knowledgable on this subject and know very littel about different types of data structures, any simple help would be great!</p>
  
  <p>My current code is:</p>
  
  <pre><code>import java.util.*;
  import java.lang.*;
  import java.io.*;
  
  class My2dPoint {
    double x;
    double y;
  
    public My2dPoint(double x1, double y1) {
      x=x1;
      y=y1;
    }
  
  }
  
  
  class CompareByX implements Comparator&lt;My2dPoint&gt; {
      public int compare(My2dPoint p1, My2dPoint p2) {
      if (p1.x &lt; p2.x) return -1;
          if (p1.x == p2.x) return 0;
          return 1;
      }
  }
  
      /* An object of the above comparator class is used by java.util.Arrays.sort() in main to sort an array of points by x-coordinates */
  
  class Auxiliaries {
  
      public static double distSquared(My2dPoint p1, My2dPoint p2) {
          double result;
          result = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
          return result;
      }
  
  }
  
  public class HW3 {
      public static void main (String argv []) throws IOException {
          int range = 1000000; // Range of x and y coordinates in points
  
          System.out.println("Enter the number of points");
  
          InputStreamReader reader1 = new InputStreamReader(System.in);
          BufferedReader buffer1 = new BufferedReader(reader1);
          String npoints = buffer1.readLine();
          int numpoints = Integer.parseInt(npoints);
  
          // numpoints is now the number of points we wish to generate
  
          My2dPoint inputpoints [] = new My2dPoint [numpoints];
  
          // array to hold points
  
          int closest [] = new int [numpoints];
  
          // array to record soln; closest[i] is index of point closest to i'th
  
          int px, py;
          double dx, dy, dist;
          int i,j;
          double currbest;
          int closestPointIndex;
          long tStart, tEnd;
  
          for (i = 0; i &lt; numpoints; i++) {
  
            px = (int) ( range * Math.random());
            dx = (double) px;
            py = (int) (range * Math.random());
            dy = (double) py;
            inputpoints[i] = new My2dPoint(dx, dy);
  
          }
  
          // array inputpoints has now been filled
  
  
  
          tStart = System.currentTimeMillis();
  
          // find closest [0]
  
  
          closest[0] = 1;
          currbest = Auxiliaries.distSquared(inputpoints[0],inputpoints[1]);
          for (j = 2; j &lt; numpoints; j++) {
             dist = Auxiliaries.distSquared(inputpoints[0],inputpoints[j]);
             if (dist &lt; currbest) {
                 closest[0] = j;
                 currbest = dist;
             }
          }
  
          // now find closest[i] for every other i 
  
          for (i = 1; i &lt; numpoints; i++) {
              closest[i] = 0;
              currbest = Auxiliaries.distSquared(inputpoints[i],inputpoints[0]);
              for (j = 1; j &lt; i; j++) {
                dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
                if (dist &lt; currbest) {
                 closest[i] = j;
                 currbest = dist;
            }
              }
  
              for (j = i+1; j &lt; numpoints; j++) {
                dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
                if (dist &lt; currbest) {
            closest[i] = j;
                    currbest = dist;
            }
              }
          }
  
          tEnd = System.currentTimeMillis();
          System.out.println("Time taken in Milliseconds: " + (tEnd - tStart));
      }
  }
  </code></pre>