Computer Programming

How do I find k nearest neighbours of a given point from a set of points in a plane in O(n)?

Let’s call the given point be P and set of points be S. Iterate over S and find distance between each point in S and P using Euclidean distance formula (d = √[(x2 β€“ x1)2 + (y2 β€“ y1)2]). Store these distances in an array. Let’s call this array distances[]. Most obvious solution, seems to sort this array distances[] and get first k nearest neighbours. This algorithm is π‘‚(π‘›π‘™π‘œπ‘”π‘›). Here’s a C++ code:

//How do I find k nearest neighbours of a given point?
//Created by Himanshu on 08/07/21.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#define N 5
using namespace std;

struct Point {
    int pos;
    double distance;
};

bool comp(const Point &a, const Point &b) {
    return (a.distance < b.distance);
}

void solve(int inpPoints[N][2], int inpPoint[2], int k) {
    
    vector<vector<int>> nearestNeighbours(k, vector<int> (2, 0));
    
    struct Point points[N];
    for (int i=0; i<N; i++) {
        points[i].distance = sqrt(((inpPoints[i][0]-inpPoint[0])*(inpPoints[i][0]-inpPoint[0])) + ((inpPoints[i][1]-inpPoint[1])*(inpPoints[i][1]-inpPoint[1])));
        points[i].pos = i;
    }
    sort(points, points+N, comp);
    printf("%d nearest neighbours to Point(0, 0) are\n", k);

    for (int i=0; i<k; i++) {
        cout<<inpPoints[points[i].pos][0]<<" "<<inpPoints[points[i].pos][1]<<"\n";
        nearestNeighbours[i].push_back(inpPoints[points[i].pos][0]);
        nearestNeighbours[i].push_back(inpPoints[points[i].pos][1]);
    }
}

int main() {
    
    int k = 2;
    int points[N][2] = { {8, 4}, {2, 5}, {1, 1}, {2, 8}, {7, 1} };
    int point[] = {0, 0};
    solve(points, point, k);
    return 0;
}

Also Read: https://www.aureollabs.com/n-queen-problem-analysis/

But we can do better than that. We can solve this in π‘‚(𝑛).

Make a min heap out of this array distances[]. This step is π‘‚(𝑛). (You can read more about binary heap here.) Now, extract minimum element from this heap using extractMin operation of heap. Operation extractMin takes π‘‚(π‘™π‘œπ‘”π‘›) time. Calling it k times, you get the running time as π‘‚(𝑛+π‘˜π‘™π‘œπ‘”π‘›).

Here’s a C++ program using Heap provided by C++ library:

//How do I find k nearest neighbours of a given point in O(n)?
//Created by Himanshu on 08/07/21.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#define N 5
using namespace std;

struct Point {
    int pos;
    double distance;
};

bool comp(const struct Point &a, const struct Point &b) {
    return (a.distance > b.distance);
}

void solve(int inpPoints[N][2], int inpPoint[2], int k) {
    
//    vector<vector<int>> nearestNeighbours(k, vector<int> (2, 0));
//

    vector<struct Point> points;
    for (int i=0; i<N; i++) {
        Point point;
        point.distance = sqrt(((inpPoints[i][0]-inpPoint[0])*(inpPoints[i][0]-inpPoint[0])) + ((inpPoints[i][1]-inpPoint[1])*(inpPoints[i][1]-inpPoint[1])));
        point.pos = i;
        points.push_back(point);
    }
    make_heap(points.begin(), points.end(), &comp);
    
    
    printf("K nearest neighbours to Point(0, 0) are\n");
    for (int i=0; i<k; i++) {
        struct Point point = points.front();
        pop_heap(points.begin(), points.end(), &comp);
        points.pop_back();
        cout<<inpPoints[point.pos][0]<<" "<<inpPoints[point.pos][1]<<"\n";
        
    }
    
}

int main() {
    
    int k = 2;
    int points[N][2] = { {8, 4}, {2, 5}, {1, 1}, {2, 8}, {7, 1} };
    int point[] = {0, 0};
    solve(points, point, k);
    return 0;
}

Thanks.