Flip-algorithm for constructing the Delaunay triangulation / Voronoi diagram in $$$O(n^2)$$$

Правка en5, от VitaliiV, 2025-12-03 07:37:16

Hello everyone! Recently I wanted to solve the problem 102482G - Panda Preserve, and I couldn’t find a simple implementation of Delaunay triangulation anywhere.

In this blog I want to talk about what a Delaunay triangulation is, what a Voronoi diagram is, how they are related, and how they can be constructed without using complex data structures.

Let’s begin with several definitions and facts:

A triangulation is a partition of some set of points S into triangles such that the interior regions of the triangles do not intersect.

A Delaunay triangulation is such a partition of a set of points S into triangles that inside the circumcircle of each triangle there are no points from the set.

A Voronoi diagram is a partition of the plane in which each region consists of points that are closer to one element of the set S than to any other element.

The Voronoi diagram and the Delaunay triangulation are dual graphs.

Delaunay triangulation construction algorithm in $$$O(n^2)$$$

First of all, it’s worth mentioning that the Delaunay triangulation can be constructed much faster than in $$$O(n^2)$$$. You can read more about this here. However, the Fortune algorithm presented there is too difficult to understand and writing it during a contest is extremely hard.

The $$$O(n^2)$$$ implementation is quite simple in terms of ideas and consists of 2 steps.

Step 1

We construct an arbitrary triangulation of the given set of points. This construction is similar to constructing a convex hull. Among all points of the set, we find the point with the smallest x-coordinate, and if there are several, then the one with the smallest y-coordinate. Let this point be p. Shift all coordinates so that point p ends up at the origin. Compute the polar angles of all points relative to p to sort them around it.

We will build the triangulation in 2 phases:

In the first phase, we connect all points with point p and also connect neighboring points with each other. If it were guaranteed that the initial set of points forms a convex polygon, this would already be sufficient, but this is not guaranteed.

In the second phase, we act similarly to the Graham’s algorithm for constructing the convex hull. Each time we add a new point, we must check whether the convexity condition is violated. If it is violated, then we have found a “dent” that must be filled.

In this example, when attempting to add vertex 3 to the convex hull, it turns out that the convexity condition is violated, and triangle 123 must be added to the triangulation.

Step 2

We already have some triangulation of the set of points, but it does not yet satisfy the criteria of a Delaunay triangulation. We will iteratively improve our triangulation. At each step, we search for a quadrilateral ABCD such that it contains the edge AC, and triangles ABC and ACD do not satisfy the Delaunay criterion. The flip operation removes edge AC and adds edge BD. For example, if initially we had triangles ABC and ACD, then after applying the operation we get triangles ABD and BCD. It can be proven that if the initial partition does not satisfy the Delaunay criterion, then a flip fixes this. For brevity, I will not give this proof here. This process repeats until all edges satisfy the Delaunay criterion.

Example of the flip operation.

Connection with the Voronoi diagram

In fact, having the Delaunay triangulation, building the Voronoi diagram is very easy. For each triangle, find the center of its circumcircle, connect the centers of circumcircles of adjacent triangles, and draw rays to infinity for those triangles that have no neighbors.

Connection between the Voronoi diagram and the Delaunay triangulation (black lines — Delaunay triangulation, red lines — Voronoi diagram).

Generalization

The iterative flip algorithm runs in $$$O(n^2)$$$ in the worst case, because in the worst case up to $$$O(n)$$$ flip operations may be required for each of the $$$O(n)$$$ edges that can undergo a flip. As already mentioned, there exist much faster and more precise ways to find the Delaunay triangulation, but this algorithm is simpler to understand and can be written in 30–40 minutes.

Here I provide the implementation of the algorithm, although, even though this code passed all tests of 102482G - Panda Preserve, if I were the reader I would still write it myself.

Tool, where you can visualize different triangulations produced by this code.

Code

If you have any corrections or additions, write them in the comments.

Теги geometry, tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский VitaliiV 2025-12-03 08:52:29 19 Tiny change: 'am).\n\n**Generalization**\n\nThe ' -> 'am).\n\n**Summary**\n\nThe '
en9 Английский VitaliiV 2025-12-03 08:06:32 4
en8 Английский VitaliiV 2025-12-03 07:45:08 12
en7 Английский VitaliiV 2025-12-03 07:41:32 4
en6 Английский VitaliiV 2025-12-03 07:41:22 152
en5 Английский VitaliiV 2025-12-03 07:37:16 46 Tiny change: 'bout this х[here](htt' -> 'bout this [here](htt' (published)
en4 Английский VitaliiV 2025-12-03 07:32:36 57
en3 Английский VitaliiV 2025-12-03 07:31:40 7477 Tiny change: 's ABD and BCD. It can b' -> 's ABD and **BCD**. It can b'
en2 Английский VitaliiV 2025-12-03 07:24:10 102
en1 Английский VitaliiV 2025-12-03 07:21:34 4608 Initial revision for English translation (saved to drafts)
ru42 Русский VitaliiV 2025-12-02 20:28:55 2 Мелкая правка: ' алгоритм фортуна, пр' -> ' алгоритм Фортуна, пр'
ru41 Русский VitaliiV 2025-12-02 20:26:28 119
ru40 Русский VitaliiV 2025-12-02 20:19:02 4 Мелкая правка: 'о — такое раз' -> 'о — это такое раз'
ru39 Русский VitaliiV 2025-12-02 20:18:25 4
ru38 Русский VitaliiV 2025-12-02 20:18:12 13 Мелкая правка: ' операций флипа на каждый' -> ' операций flip на каждый'
ru37 Русский VitaliiV 2025-12-02 20:16:37 4
ru36 Русский VitaliiV 2025-12-02 20:16:25 44
ru35 Русский VitaliiV 2025-12-02 20:14:46 22
ru34 Русский VitaliiV 2025-12-02 20:13:45 80
ru33 Русский VitaliiV 2025-12-02 20:11:38 6 Мелкая правка: 'овести до \(O(n)\) операций ' -> 'овести до $O(n)$ операций '
ru32 Русский VitaliiV 2025-12-02 20:04:15 2 Мелкая правка: 'бщение**\nИтератив' -> 'бщение**\n\nИтератив'
ru31 Русский VitaliiV 2025-12-02 20:01:31 0 (опубликовано)
ru30 Русский VitaliiV 2025-12-02 20:01:03 1 Мелкая правка: ' проверить не наруша' -> ' проверить, не наруша'
ru29 Русский VitaliiV 2025-12-02 20:00:29 45
ru28 Русский VitaliiV 2025-12-02 19:59:10 255
ru27 Русский VitaliiV 2025-12-02 19:45:44 1 Мелкая правка: ' построить не исполь' -> ' построить, не исполь'
ru26 Русский VitaliiV 2025-12-02 19:44:58 1 Мелкая правка: 'зать о том что такое' -> 'зать о том, что такое'
ru25 Русский VitaliiV 2025-12-02 19:43:20 26
ru24 Русский VitaliiV 2025-12-02 19:42:43 125
ru23 Русский VitaliiV 2025-12-02 19:38:27 79
ru22 Русский VitaliiV 2025-12-02 19:37:44 116
ru21 Русский VitaliiV 2025-12-02 19:35:44 74
ru20 Русский VitaliiV 2025-12-02 19:32:56 2 Мелкая правка: 'полнить.\n![ ](htt' -> 'полнить.\n\n![ ](htt'
ru19 Русский VitaliiV 2025-12-02 19:32:40 173
ru18 Русский VitaliiV 2025-12-02 19:32:14 160
ru17 Русский VitaliiV 2025-12-02 19:31:58 2 Мелкая правка: '/ris1.png)На рисунке' -> '/ris1.png)\nНа рисунке'
ru16 Русский VitaliiV 2025-12-02 19:31:39 82
ru15 Русский VitaliiV 2025-12-02 19:31:23 238 Мелкая правка: 'полнить.\n\n![](https://' -> 'полнить.\n![ ](https://'
ru14 Русский VitaliiV 2025-12-02 19:27:11 382
ru13 Русский VitaliiV 2025-12-02 19:04:05 25
ru12 Русский VitaliiV 2025-12-02 19:03:40 8
ru11 Русский VitaliiV 2025-12-02 18:55:34 602
ru10 Русский VitaliiV 2025-12-02 18:50:10 7 Мелкая правка: '0%D1%84)\n[cut]\n\n\n**Ал' -> '0%D1%84)\n\n\n**Ал'
ru9 Русский VitaliiV 2025-12-02 18:49:59 4 Мелкая правка: 'n[cut]\n\n**Алго' -> 'n[cut]\n\n\n**Алго'
ru8 Русский VitaliiV 2025-12-02 18:49:42 8407 Мелкая правка: 'а $O(n^2)$в худшем с' -> 'а $O(n^2)$ в худшем с'
ru7 Русский VitaliiV 2025-12-02 18:38:24 784
ru6 Русский VitaliiV 2025-12-02 18:26:53 1490 Мелкая правка: '[0, 2 $\pi \)' -> '[0, 2 $\pi\)'
ru5 Русский VitaliiV 2025-12-02 18:07:01 5 Мелкая правка: '0%D1%84)\n\n**Свойст' -> '0%D1%84)\n[cut]\n**Свойст'
ru4 Русский VitaliiV 2025-12-02 18:06:43 376
ru3 Русский VitaliiV 2025-12-02 18:02:15 811 Мелкая правка: 'роного за O(n^2)\nТриангул' -> 'роного за $O(n^2)$\nТриангул'
ru2 Русский VitaliiV 2025-12-02 17:48:11 448
ru1 Русский VitaliiV 2025-12-02 17:38:34 43 Первая редакция (сохранено в черновиках)