I can not decide the fastest way to pick the k nearest points to some point P from an n-points set. My guesses are below:

1. Compute the n-distance, order it and pick the k smallest values;
2. Compute pointwise distance and update a k-sized point stack;

Any other manners are welcome.

CodePudding user response：

Getting the median is O(n) operation, thus the whole problem has minimum complexity of O(n) - compute all distances and find the kth smallest element partitioning the whole set by this threshold.

One can also work in chunks of K >> k. The maximum of the first k distances works as a preliminary threshold: all the points further than that do not need to be considered. One will instead place all the points smaller than that into an array, and after the array size is close to K, one can use the kth element linear algorithm to re-partition the array.

CodePudding user response：

Finding the smallest k elements is O(n), for any value of k. It's O(n log k) if you need the k elements to be sorted. This is the Partition Algorithm.

You're best off reading the algorithm on Wikipedia. It's quicksort, but you only need to 'recurse' on one side because the other side is guaranteed to be completely out or completely in. There are expensive tricks that guarantee O(n log n) instead of that merely being the average.