Fast way to calculate k nearest points to point P

Question

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.

Answer 1

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.