How to Efficiently Find a Neighbor Point in a List?

I have a large list of Points in an Image and I want to find the Point Nearest to a given Point.

Existing Approach Tried: Divide the Image into Tiles and search only within the Region of Interest by building a Table. The light blue cloured one are the points I'm comparing.

Problems Even with very fewer comparisons, my algorithm is taking more than the actual time. Is there any scope for improvement in my current approach? Is there any other better approach?

Run Times in my Machine: Time Taken for

FindNearestPoint  : 0.021145 ms  
FindNearestPointV2: 0.047953 ms

PC Config: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70 GHZ

// Feature Comparision.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include "Timer.h" //http://www.songho.ca/misc/timer/files/timer.zip

#include "opencv2\opencv.hpp"
#include "opencv2\opencv_modules.hpp"

using namespace cv;
using namespace std;

bool FindNearestPoint(const Point2f Point, const vector<Point2f>vPoints, int &Index )
{
    CV_Assert(vPoints.size() != 0);

    float PrevDistance = FLT_MAX;
    Index = -1;//Error Case
    for (size_t i = 0; i < vPoints.size(); i++)
    {
        float Distance = cv::norm(Point - Point2f(vPoints[i].x, vPoints[i].y));

        if (Distance < PrevDistance)
        {
            Index = i;
            PrevDistance = Distance;
        }
    }
    return true;

}

static inline bool GetListofClustersToProcess(const Point2f Pt, const Point2f szTileSize, const Size GridSize, vector<Point> &ClusterIndices)
{
    Point Index(Pt.x* szTileSize.x, Pt.y * szTileSize.y);
    vector<Point> vClusterIndices;

    //Prev Tile
    vClusterIndices.push_back(Index + Point(-1, -1));//Prev Tile
    vClusterIndices.push_back(Index + Point(-1, 0)); //Curr Tile
    vClusterIndices.push_back(Index + Point(-1, 1)); //Next Tile

    vClusterIndices.push_back(Index + Point(0, -1)); //Prev Tile
    vClusterIndices.push_back(Index + Point(0, 0)); //Curr Tile
    vClusterIndices.push_back(Index + Point(0, 1)); //Next Tile

    vClusterIndices.push_back(Index + Point(1, -1)); //Prev Tile
    vClusterIndices.push_back(Index + Point(1, 0));     //Curr Tile
    vClusterIndices.push_back(Index + Point(1, 1));     //Next Tile

    for (size_t i = 0; i < vClusterIndices.size(); i++)
    {
        Index = vClusterIndices[i];
        if ((Index.x < 0) || (Index.x >= GridSize.width) || (Index.y < 0) || (Index.y >= GridSize.height))
        {
            continue;
        }
        ClusterIndices.push_back(Index);
    }

    return true;
}

bool FindNearestPointV2(const Point2f Point, const vector<Point2f>vPoints,const vector<vector<vector<int>>>vClusters,const Point2f szTileSize, const Size GridSize, int &Index,Mat &mDebugImage)
{
    #define EnableDebug 0

    CV_Assert(vPoints.size() != 0);

    vector<cv::Point> ClusterIndices;
    ClusterIndices.clear();

    GetListofClustersToProcess(Point, szTileSize,GridSize, ClusterIndices);

    float PrevDistance = FLT_MAX;

    Index = -1;//Error Case
    int KeypointIdx = 0;

    for (size_t iClusterIdx = 0; iClusterIdx < ClusterIndices.size(); iClusterIdx++)
    {
        cv::Point Cluster(ClusterIndices[iClusterIdx]);

        CV_Assert((Cluster.x >= 0)&&(Cluster.x < GridSize.width));
        CV_Assert((Cluster.y >= 0) && (Cluster.y < GridSize.height));

        for (size_t i = 0; i < vClusters[Cluster.y][Cluster.x].size(); i++)
        {
            KeypointIdx = vClusters[Cluster.y][Cluster.x][i];

            CV_Assert(KeypointIdx < vPoints.size());

            float Distance = cv::norm(Point - Point2f(vPoints[KeypointIdx].x, vPoints[KeypointIdx].y));

#if EnableDebug
            circle(mDebugImage, vPoints[KeypointIdx], 2, Scalar(255, 255, 0), 2);

            imshow("Input Features", mDebugImage);
#endif
            //New Optimized Implementation
            //waitKey();

            if (Distance < PrevDistance)
            {
                Index = KeypointIdx;
                PrevDistance = Distance;
            }
        }
    }
    return true;

}

int main(int argc, char* argv[])
{
    /*TestKNN();
    return 0;*/

    Size ImageSize(900, 300);
    Mat mInputImage(ImageSize, CV_8UC3, Scalar::all(0));
    RNG rng(0xFFFFFFFF);
    vector<Point2f>vKeypoints;
    int MaxNoOfKeypoints = 2000;
    uint16_t maxFilteredKeypoints = 350;
    int TileSize = 32;//Tile Size in Pixels
    Size GridSize((ImageSize.width / TileSize)+1, (ImageSize.height / TileSize)+1);
    vector<vector<vector<int>>>vClusters;
    Point ptTileIdx(0,0);
    Point2f PtQuery,PtNearestPoint, PtNearestPointV2;
    Point2f GridScale((float)GridSize.width / (float)ImageSize.width, (float)GridSize.height / (float)ImageSize.height);
    int NoOfTestPoints = 100, Iteration = 0;

    for (;;)
    {
        vKeypoints.clear();
        vClusters.clear();
        mInputImage.setTo(0);
        //Generating Random Keypoints
        for (size_t i = 0; i < MaxNoOfKeypoints; i++)
        {
            vKeypoints.push_back(Point2f(rng.uniform(0, ImageSize.width), rng.uniform(0, ImageSize.height)));
        }

        cout << "Grid Size :" << GridSize << "\n";
        for (size_t iVerTile = 0; iVerTile < GridSize.height; iVerTile++)
        {
            vector<vector<int>>HorTiles;
            Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
            for (size_t iHorTile = 0; iHorTile < GridSize.width; iHorTile++)
            {
                Rect TileRect(iHorTile*TileSize, iVerTile*TileSize, TileSize, TileSize);
                rectangle(mInputImage, TileRect, color, 1);
                color += Scalar(0, 0, 10);
                HorTiles.push_back(vector<int>());
            }
            vClusters.push_back(HorTiles);
        }
        printf("Cluster Size : %d , %d \n",vClusters.size(),vClusters[0].size());
        
        //Classify Tile Idx for all the Keypoints
        for (size_t i = 0; i < MaxNoOfKeypoints; i++)
        {
            ptTileIdx.x = (int)(vKeypoints[i].x / TileSize);
            ptTileIdx.y = (int)(vKeypoints[i].y / TileSize);
            vClusters[ptTileIdx.y][ptTileIdx.x].push_back(i);
        }

        //Displaying the Keypoints
        for (size_t i = 0; i < MaxNoOfKeypoints; i++)
        {
            circle(mInputImage, vKeypoints[i], 2, Scalar(255, 0, 0), 2);
        }
        Mat mInputTestImage = mInputImage.clone();
        Iteration = 0;
        while (Iteration<NoOfTestPoints)
        {
            PtQuery = Point2f(rng.uniform(0, ImageSize.width), rng.uniform(0, ImageSize.height));

            circle(mInputTestImage, PtQuery, 4, Scalar(0, 255, 0), 4);
            circle(mInputTestImage, PtQuery, 2, Scalar(0, 0, 255), 2);
            
            int NearestPointIndex = -1, NearestPointIndexV2 = -1;
            Timer t_FindNearestPt;
            t_FindNearestPt.start();

            FindNearestPoint(PtQuery, vKeypoints, NearestPointIndex);

            t_FindNearestPt.stop();

            PtNearestPoint = vKeypoints[NearestPointIndex];

            Timer t_FindNearestPtV2;
            t_FindNearestPtV2.start();
            //New Optimized Implementation
            FindNearestPointV2(PtQuery, vKeypoints, vClusters, GridScale, GridSize, NearestPointIndexV2,mInputTestImage);

            t_FindNearestPtV2.stop();

            PtNearestPointV2 = vKeypoints[NearestPointIndexV2];

            if (NearestPointIndexV2 != -1)
            {
                circle(mInputTestImage, PtNearestPointV2, 2, Scalar(0, 0, 255), 2);
            }
            if (NearestPointIndex != -1)
            {
                circle(mInputTestImage, PtNearestPoint, 2, Scalar(0, 255, 0), 2);
            }

            if (NearestPointIndex != NearestPointIndexV2)
            {
                printf("[Error] Closest Point not Matching! \n");
                cout << "Point" << PtQuery <<  " Org" << PtNearestPoint << "!= V2 " << PtNearestPointV2 << "\n";
                float Distance = cv::norm(PtQuery - PtNearestPoint);
                float DistanceV2 = cv::norm(PtQuery - PtNearestPointV2);
                printf("Distance : %f - %f  \n", Distance, DistanceV2);
            }
            /*else
            {
                printf("[Passed] Closest Point Matching! \n");
            }*/
            float TimeTaken_C = t_FindNearestPt.getElapsedTimeInMilliSec();
            printf("Time Taken for FindNearestPoint  : %f ms\t", TimeTaken_C);
            printf("FindNearestPointV2: %f ms\t", t_FindNearestPtV2.getElapsedTimeInMilliSec());
            printf("Speed: %f x\n", TimeTaken_C/t_FindNearestPtV2.getElapsedTimeInMilliSec());

            imshow("Input Features", mInputTestImage);
            Iteration++;
            char key = (char)waitKey();
            if (key == 27 || key == 'q' || key == 'Q') // 'ESC'
                break;
            mInputTestImage= mInputImage.clone();
        }
    
        char key = (char)waitKey();
        if (key == 27 || key == 'q' || key == 'Q') // 'ESC'
            break;
    }


    return 0;
}