0

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)?

User1291
  • 7,664
  • 8
  • 51
  • 108

1 Answers1

1

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.

EDIT: 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

Geom
  • 827
  • 4
  • 15
  • Hm ... this doesn't really adress my question. Why do I want to retrieve the voronoi cell anyway? I mean in my mind, the great thing about Voronoi is that if I know the cell my query point is in, I know exactly what site is closest to my query point. But if all I'm interested in is the nearest site and I can find that via the delaunay triangulation easily enough ... why do I need Voronoi at all? – User1291 Jun 23 '21 at 11:10
  • 1
    If you are only interested in nearest neighbor queries you don't need Voronoi cells. But you asked why one could need a Voronoi diagram at all. This is the case for algorithms which are interested in the boundary or in the area of a Voronoi cell. Find just two examples here: https://en.wikipedia.org/wiki/Centroidal_Voronoi_tessellation and here: https://en.wikipedia.org/wiki/Natural_neighbor_interpolation – Geom Jun 23 '21 at 13:43
  • Thanks, that's what I was looking for. :) Could you incorporate your comment about when you actually use Voronoi diagrams into your answer? – User1291 Jun 23 '21 at 16:23