I am faced with the problem to find the closest 100 points for each 1 000 000 points in an array. Points are 2D with x and y coordinates. What I have in mind is only the brute force way using the Euclidean distance, which even multithreaded will take way too long.
Right now I have a Point class that implements Runnable containing x and y. Coordinates could be nagative and positive numbers.
Can someone suggest or write an algorithm, or just give some ideas on how I can improve performance.
One of the way i see it would be to do it through an adjacency matrix, that way, each element k would have to calculate n-k distances (as you can reuse previously computed distances from past elements).
you go from the brute force way of O(nn) to something somewhat lower though that would require the computer to store a 106x106 matrix that you would need to quicksort or something afterward.
another way (which might be better) would be to calculate for each point their distance to [0,0], sort the array by this distance then for each point calculate the distance to the adjacent points in the array
