Find K nearest Points to Point P in 2-dimensional plane

Question

Source: AMAZON INTERVIEW QUESTION

Given a point P and other N points in two dimensional space, find K points out of the N points which are nearest to P.

What is the most optimal way to do this ?

This Wiki page does not provide much of help in building a algorithm.Any ideas/approaches people.

Answer 1

Solution 1 make heap of size K and collect points by minimal distance O(NLogK) complexity.

Solution 2: Take and array of size N and Sort by distance. Should be used QuickSort (Hoare modification). As answer take first K points. This is too NlogN complexity but it is possible optimize to approximate O(N). If skip sorting of unnecessary sub arrays. When you split array by 2 sub arrays you should take only array where Kth index located. complexity will be : N +N/2 +N/4 + ... = O(N).

Solution 3: search Kth element in result array and takes all point lesser then founded. Exists O(N) alghoritm, similar to search of median.

Notes: better use sqr of distance to avoid of sqrt operations, it will be greater faster if point has integer coordinates.

As interview answer better use Solution 2 or 3.