So if this is true: How to query a Voronoi diagram?
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.
How do we actually use them?
I mean, I am aware of the Delaunay-based search tree that I can construct for it, but I don't need a Voronoi diagram to construct a Delaunay Triangulation now, do I?
So what practical purposes - except, say, printing it on a map for easier human digestion - does Voronoi serve?
What problems can be solved with just a Voronoi Diagram without its dual (in a more efficient manner than without it, of course)?
It depends on the access pattern. Since the two graphs are dual, both contain basically the same information. From practical experience, however, computing the Voronoi vertices requires expensive multiple-precision arithmetic on a case-by-case basis, since there are degenerate settings and since there are infinite and nearly-infinite Voronoi cells. Therefore, depending on the access pattern, it will often be more efficient to compute the Voronoi diagram once instead of using the Delaunay triangulation and computing its dual elements over and over again.
On the other hand, nearest neighbor search in a Delaunay triangulation is much simpler, thus I have chosen a hybrid data representation for my Voronoi diagram. It uses the Delaunay triangulation and a Voronoi representation on top of it and so points can be located in O(log(n)) time. The performance indicates that this is a good approach: for one million queries in a Voronoi diagram with n=1000 sites, only 0.3 seconds are needed.
For nearest neighbor queries you don't need Voronoi cells. But for algorithms which are interested in the boundary or in the area of a Voronoi cell. Just a few examples: Centroidal Voronoi Tesselation, Natural Neighbor Interpolation, Medial Axis