How to query a Voronoi diagram?

Question

I am using boost to compute the voronoi diagram of a set of points in 2-D, very straightforward;

std::vector<Point> points;
...
voronoi_diagram<double> vd;
construct_voronoi(points.begin(), points.end(), &vd);

Is there an algorithm to process the resulting polygons such that the query "Which site does a given point belong to?" can be answered in constant time? In other words, in which polygon a given point is located among a set of polygons?

Of course one can calculate and compare the distance of the given point to the existing ones but that would take O(n) time and does not make use of the information encoded in the Voronoi diagram.

Answer 1

The question "Which site does a given point belong to?" is just another way of stating the nearest neighbor search problem: the relevant Voronoi polygon is the one associated with the nearest point in the set generating the Voronoi diagram. Unfortunately,

• there isn't any constant time algorithm for solving this problem, and
• the Voronoi diagram doesn't provide any solving the problem faster than an O(N) search.

If you need to locate many points in the Voronoi diagram, you can build a search tree and usually get O(log N) performance. The answer on this question does this in python building a k-d tree to do the query. In boost, you can use the existing R-tree for this purpose.

There is a way to build a search tree based on Voronoi diagrams (the Delaunay hierarchy). It maybe could provide some minor benefits if you also use it to build the Voronoi diagram. But there aren't optimized libraries easily available like there are for the generic search problem.