Construct an O(n) average case algorithm to find closest m points from a list of n points

Question

We need to construct an algorithm, given a list of n points in the Cartesian plane, the closest m (m is not constant, and less than or equal to n) points to the origin. This algorithm needs to work in O(n) average time, which is what I've been struggling with.

My initial idea was to sort the list based on the distance of each point from the origin, and select the first $m$ points from the sorted list. However, all the sorting algorithms I know work in O(nlogn) average time. Is there another way to do this, using the properties of the cartesian plane?

Thanks for any help.

Answer 1

Use the QuickSelect algorithm to find the m-th closest point to the origin. This will leave the list partitioned into the closest m points, followed by the farther points.