Find nearest k points from the central point

Question

The task:

Given a list of points, a central point, and an integer k, find the nearest k points from the central point.

For example, given the list of points [(0, 0), (5, 4), (3, 1)], the central point (1, 2), and k = 2, return [(0, 0), (3, 1)].

My solution:

const lst = [[0, 0], [5, 4], [3, 1]];
const center = [1, 2];
const k = 2;

const findNearestPoints = ({lst, center, k}) => {
  // I assume the data are valid; no error checks
  const calcHypo = x => Math.sqrt((x[0] - center[0])**2
                                + (x[1] - center[1])**2);
  const sortPoints = (a,b) => calcHypo(a) - calcHypo(b);
  return lst
   .sort(sortPoints)
   .slice(0,k);
};

console.log(findNearestPoints({lst, center, k}));

Answer 1

Don't sqrt the distance.

It is a common mistake when filtering distances to use the complete distance calculation.

Given 2 values a and b, if a < b then it is also true that sqrt(a) < sqrt(b). Hence you don't need the expensive sqrt calculation to know the if a point is closer than another.

To find the closest the following does not use the sqrt of the distance.

function closestPoint(points, point, dist){
    var x, y, found, min = dist * dist; // sqr distance
    for(const p of points) {
        x = p[0] - point[0];
        y = p[1] - point[1];
        x *= x;
        y *= y;
        if(x + y < min){
            min = x + y;
            if (min === 0) { return p } // early exit
            found = p;
        }
    }
    return found;

}

Not in the sort!!!

You are doing the distance calculation in the sort DON'T!!!, that means you repeat the same calculations over and over.

To improve you throughput the following will reduce the over all time. The improvement is linear and does not change the complexity.

Note that in JS a ** 2 is slightly slower than a * a

A more efficient version of your solution

function findNearestPoints({list, center, k}) {
    const res = [];
    const cx = center[0], cy = center[1]; // alias and reduce indexing overhead
    const distSqr = (x, y) => (x -= cx) * x + (y -= cy) * y;
    const sort = (a, b) => a[1] - b[1];

    for (const p of list) { res.push([p, distSqr(p[0], p[1])]) }
    res.sort(sort).length = k;
    return res.map(p => p[0]);
}

The ** operator for roots

Note that JS has the ** operator. That you can use it to get roots by making the right side the inverse, 1 over the power. Thus the sqrt is **(1/2) the cube root is **(1/3)

eg

if 2 ** 2 === 4 then 4 ** (1/2) === 2
if 2 ** 3 === 8 then 8 ** (1/3) === 2  Don't approximate 8 ** 0.33 !== 2
if 2 ** 4 === 16 then 16 ** (1/4) === 2

Better sort

The sort is the bottle neck in this problem.

You can use a binary tree sort as it is the least complex for real numbers (every coder should learn how to implement a binary tree sort)

Do you need the sort?

However I think (think means might be, I am going by instinct) that there is a faster solution that does not involve a sort and that is at most \$O(n)\$

Remember that the order of the points is not important, that you need only separate the points in two. It may take a few passes to do, but as long as the number of passes is not related to the number of points or 'k' you will have a \$O(n)\$ solution.

I am not going to give you the solution this time (if there is one) as there is no problem solving experienced gained coping code.

Answer 2

Use a max-heap of at most k elements. Loop through all of the n points computing their (squared) distances to the central point. If the root of node of the heap is farther from the central point than the i'th of the n points, then discard the root and heapify with the i'th. This has time complexity n*log(k) rather than n*log(n) which is a huge difference if n >> k.

Answer 3

The answers here are great, especially if you're looking to implement this algorithm in a faster way (which would be very important to do if there could potentially be a lot of points - the current implementation would be slow on large lists).

...however, I didn't see anything in the problem description about speed being a needed factor. I tend to put code quality first, avoid premature optimizations, and only speed up the code when its needed. (i.e. if there's only ever going to be at most 5 points in the list, then many speed improvements end up becoming overhead that slows the algorithm down instead of speeding it up!)

With that in mind, I actually really like the way you implemented it. It's clear and easy to understand. I'll just add a couple suggestions:

• Like others have already pointed out, you can use Math.abs()
• I would copy the array of points before sorting them - .sort() modifies the original array, and you generally don't want to modify function parameters.

Here's my version:

const distanceBetween = ([x1, y1], [x2, y2]) => Math.hypot(x1 - x2, y1 - y2);

const findNearestPoints = ({points, center, numberOfResults}) => {
  const distanceFromCenter = p => distanceBetween(p, center);
  return [...points]
   .sort((p1, p2) => distanceFromCenter(p1) - distanceFromCenter(p2))
   .slice(0, numberOfResults);
};

console.log(findNearestPoints({
  points: [[0, 0], [5, 4], [3, 1]],
  center: [1, 2],
  numberOfResults: 2,
}));