[Tutorial] Fortune's Algorithm for O(n log n) Voronoi Diagram and Delaunay Triangulation

Правка en1, от Monogon, 2020-12-16 20:13:46

What's a Voronoi Diagram?

Given a set $$$S$$$ of $$$n$$$ points in the 2D plane, the Voronoi diagram is a partition of the plane into regions. The region associated with a point $$$p\in S$$$ contains precisely the points $$$q$$$ such that $$$q$$$ is closer to $$$p$$$ than any other point in $$$S$$$. In other words, a point $$$q$$$ belongs to the region of its nearest neighbor.

The Voronoi diagram can be represented by the planar graph of boundaries between regions. A vertex in this graph is where three or more segments meet (or a point at infinity), and an edge is a segment connecting two of these vertices. The way the regions were defined, we see that a segment contains the points equidistant to two points in $$$S$$$, so it is part of their perpendicular bisector. Similarly, a Voronoi vertex is equidistant to three or more vertices in $$$S$$$, so it is their circumcenter. Recall that the circumcenter is the intersection of perpendicular bisectors.

What's a Delaunay Triangulation?

The Delaunay triangulation is the dual graph of the Voronoi diagram. That is, a Voronoi vertex is a Delaunay face and a Delaunay vertex is a Voronoi vertex. A Delaunay edge connects two points if and only if their corresponding Voronoi regions share a border.

In the following image, the set $$$S$$$ corresponds to the black points. The red vertices and edges are the Voronoi diagram. The black points and edges are the Delaunay triangulation.

The Delaunay triangulation only involves edges between existing points, while the Voronoi diagram creates new vertices and needs a way to represent edges going infinitely in one direction. For this reason, it is often more convenient to compute the Delaunay triangulation and only convert to the Voronoi diagram if needed.

Why are these useful?

The definition of the Voronoi diagram immediately shows signs of applications. Given a set $$$S$$$ of $$$n$$$ points and $$$m$$$ query points $$$p_1,\ldots, p_m$$$, we can answer for each query point, its nearest neighbor in $$$S$$$. This can be done in $$$O((n + q)\log(n+q))$$$ offline by sweeping the Voronoi diagram and query points. Or it can be done online with persistent data structures.

Other than this, the Delaunay triangulation has many amazing properties of its own that can make it extremely useful for solving problems.

  • Each point $$$p\in S$$$ is adjacent to its nearest neighbor with a Delaunay edge.
  • For each Delaunay triangle, its circumcircle does not strictly contain any points in $$$S$$$.
  • The Delaunay triangulation maximizes the minimum angle in the triangles among all possible triangulations.
  • The Euclidean minimum spanning tree is a subset of Delaunay edges.

Degenerate Cases

Because this is geometry, there are some degenerate cases I have hidden from you up to this point. The first case is when all the points in $$$S$$$ are contained in a line. In this case, the Voronoi diagram has all edges connecting two points at infinity, and the Voronoi diagram is disconnected (in all other cases it's connected). Also in this case, the dual graph is no longer a triangulation. We may still decide to represent it by the path of edges connecting the points.

Another nasty case is cocircular points. Here, there are Voronoi vertices where more than three segments intersect. In this case, the dual graph has a face with more than three sides. However, we want it to be a triangulation, so we can also say that any triangulation of such faces is valid, and we will allow non-unique Delaunay triangulations.

Algorithms

Fortune's Algorithm

Fortune's Algorithm Implementation

Теги geometry, voronoi diagrams, delaunay triangulation, fortunes algorithm

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Monogon 2020-12-17 06:57:06 8 Tiny change: 'a Voronoi vertex. A Delaun' -> 'a Voronoi region. A Delaun'
en6 Английский Monogon 2020-12-17 03:02:57 11
en5 Английский Monogon 2020-12-17 02:09:29 1790 Tiny change: '</spoiler>' -> '</spoiler>\n\nReferences\n------------------' (published)
en4 Английский Monogon 2020-12-17 01:32:36 7082 Tiny change: 'um=1520)\n\n<spoiler summary="Caravans Solution">\nugh\n</spoiler>' -> 'um=1520)\n'
en3 Английский Monogon 2020-12-17 01:05:21 3951 Tiny change: 'hm-slowed.gif"/>\n\nFor' -> 'hm-slowed.png"/>\n\nFor'
en2 Английский Monogon 2020-12-16 22:44:18 4091 Tiny change: 'rithms\n - asdf\n\nF' -> 'rithms\n * asdf\n\nF'
en1 Английский Monogon 2020-12-16 20:13:46 4155 Initial revision (saved to drafts)