3

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.

Vectorizer
  • 1,076
  • 9
  • 24
  • I faced the same problem. One approach I thought of was using 2-d segment/interval trees for the bounding boxes voronoi polygons - there won't be too many for a given point. While searching, I came across a data structure called trapezoidal maps, which promises to look up efficiently. I am yet to read up this in detail. – ranban282 Jun 16 '22 at 11:44

1 Answers1

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.

Alex
  • 1,042
  • 1
  • 8
  • 17
  • I'm still researching this problem and maybe you're right about continuous space with infinite planes, but in discrete space, one could just color the diagram with indices that point to the nearest point. This is clearly a constant time lookup algorithm. – SapphireSun Apr 09 '21 at 19:38