I have a list of coordinates and I need to find the closest coordinate to a specific point which I'll call P.

At first I tried to just calculate the distance from each coordinate to P, but this is too slow.

I then tried to store these coordinates as a quad-tree, find the leaf node that contains P, then find the closest coordinate in that leaf by comparing distances of every coordinate to P. This gives a good approximation for the closest coordinate, but can be wrong sometimes. (when a coordinate is outside the leaf node, but closer). I've also tried searching through the leaf node's parent, but while that makes the search more accurate, it doesn't make it perfect.

If it is possible for this to be done with a quad-tree, please let me know how, otherwise, what other methods/data structures could I used that are reasonably efficient, or is it even possible to do this perfectly in an efficient manner?