An answer to this question on Stack Overflow.

Question

I have non empty Set of points scattered on plane, they are given by their coordinates. Problem is to quickly reply such queries:

Give me the point from your set which is nearest to the point A(x, y)

My current solution pseudocode

query( given_point )
{
  nearest_point = any point from Set
  for each point in Set
    if dist(point, query_point) < dist(nearest_point, given_point)
      nearest_point = point
  return nearest_point
}

But this algorithm is very slow with complexity is O(N).

The question is, is there any data structure or tricky algorithms with precalculations which will dramatically reduce time complexity? I need at least O(log N)

Update

By distance I mean Euclidean distance

Answer

You can get O(log N) time using a kd-tree. This is like a binary search tree, except that it splits points first on the x-dimension, then the y-dimension, then the x-dimension again, and so on.

If your points are homogeneously distributed, you can achieve O(1) look-up by binning the points into evenly-sized boxes and then searching the box in which the query point falls and its eight neighbouring boxes.

It would be difficult to make an efficient solution from Voronoi diagrams since this requires that you solve the problem of figuring out which Voronoi cell the query point falls in. Much of the time this involves building an R*-tree to query the bounding boxes of the Voronoi cells (in O(log N) time) and then performing point-in-polygon checks (O(p) in the number of points in the polygon's perimeter).