Научно-методически статии
APPLYING DELAUNAY TRIANGULATION IN OLYMPIAD PROBLEMS
https://doi.org/10.53656/math2025-1-1-app
Резюме. Some fundamental properties of Delaunay triangulation are presented in this article. The construction of the triangulation described here has not been encountered by the authors in the known literature. The main point is to apply this triangulation in solving otherwise challenging Olympiad problems in combinatorial geometry. One of the problems in which the method is applied is from the ’Mikl´os Schweitzer’ competition, 2002. It is extremely difficult without knowing the Delaunay triangulation properties. The second problem illustrating the method is from a prestigious Russian 239 competition held in 2024. The third is from the USA team selection tests for the IMO 2024.
Ключови думи: Delaunay triangulation; combinatorial geometry; coloring; perfect matching; Mikl´os Schweitzer competition
1. Introduction
In this paper, we examine some fundamental properties of Delaunay triangulation and their applications in solving mathematical problems. For a given set \(P\) of points (nodes) in the plane, a natural question is how to partition the plane into regions (cells) such that each cell contains exactly one node \(x \in P\), and every point in that cell is closer to \(x\) than to any other node in \(P\).
Figure 1. From Voronoi diagram to Delaunay triangulation
This partitioning of the plane into such cells is called the Voronoi diagram of the nodes in \(P\).
Throughout this paper, we assume that \(P\) is a set of points in general position, meaning that no three points in \(P\) are collinear, and no four points lie on the same circle. If we connect two points in \(P\) with an edge whenever their corresponding cells in the Voronoi diagram share a common boundary, we obtain a triangulation \(T\) of the nodes in \(P\) (fig. 1).
This triangulation is known as the Delaunay triangulation (Delaunay 1934), named after Boris Delaunay, a Russian mathematician who studied this structure. It has many practical applications. For example, it is used to obtain approximate solutions to the travelling salesman problem. Many practical problems from physics and engineering hinge upon finding numerical solutions to partial differential equations. This is done by using finite element method. This method uses a mesh of the domain on which the equation is formulated. The choice of appropriate mesh (triangulation) is important for the accuracy of the resulting solution, and here Delaunay triangulation plays an important role, as it avoids narrow triangles that adversely affect the accuracy of the finite element method.
The key property of this triangulation, exploited in the problems discussed, is that the circumcircle of any triangle in \(T\) does not contain any other points of \(P\).
There are different ways to prove the existence and uniqueness of Delaunay triangulation. The method used here has not been encountered by the authors in the known literature. On the other hand, in our opinion, the idea is quite natural, as it directly builds the triangulation by starting from the convex hull of \(P\) and successively constructing triangles inward from it.
Figure 2
2. Delaunay triangulation
Let \(P\) be a set of points in the plane in general position. A triangulation of \(P\) is a partitioning of the convex hull of \(P\) into triangles with disjoint interiors such that the set of vertices of these triangles is \(P\).
A Delaunay triangulation of \(P\) is a triangulation in which the circumcircle of each triangle participating in the triangulation does not contain a point of \(P\) in its interior (fig. 2).
Existence. We will construct the Delaunay triangulation for the points in \(P\) successively, starting from the convex hull and working „from the outside in“. Let \(C_{0}=A_{1} A_{2} \ldots A_{m}\) be the convex hull of \(P\). We include the edges of \(C_{0}\) as edges of the triangulation since they are present in all possible triangulations.
For each segment \(A_{i} A_{i+1}\) of the convex hull \(C_{0}\), we can construct a circle \(k_{i}\) through \(A_{i}\) and \(A_{i+1}\), so that that it contains no other points of \(P\) on it or in its interior. Let us take one of these circles, for instance \(k_{j}\), and begin to “expand"the circle inward into \(C_{0}\), ensuring that \(A_{j}\) and \(A_{j+1}\) remain on the circle, until it encounters a point \(X \in P\). We then add the triangle \(A_{j} A_{j+1} X\) to the triangulation (fig. 3). Let us denote
\[ C_{1}:=A_{j} X A_{j+1} A_{j+2} \ldots A_{m} A_{1} \ldots A_{j-1} . \]
Note that \(C_{1}\) may no longer be a convex polygon. Furthermore, \(C_{1}\) might consist of two polygons if \(X\) coincides with some point \(A_{i}, i \notin\{j, j+1\}\). The circle \(k_{j}^{\prime}\), circumscribed around \(\triangle A_{j} A_{j+1} X\), does not contain any points of \(P\) other than \(A_{j}, A_{j+1}\) and \(X\).
We transform \(k_{j}^{\prime}\) into two other circles, \(k_{1, j}^{\prime}\) and \(k_{2, j}^{\prime}\), where \(k_{1, j}^{\prime}\) passes through \(A_{j}\) and \(X\), and \(k_{2, j}^{\prime}\) passes through \(X\) and \(A_{j+1}\) so that both circles contain no any other points of \(P\).
Figure 3
Figure 4
Let us assume that at step \(\ell \geq 1\), we have constructed the contour \(C_{\ell}=A_{1}^{\prime} A_{2}^{\prime} \ldots A_{p}^{\prime}\) and the corresponding circles \(k_{i}^{\prime}, i=1,2, \ldots, p\), such that \(k_{i}^{\prime}\) does not contain any points of \(P\) other than \(A_{i}^{\prime}\) and \(A_{i+1}^{\prime}\). We select one of these circles, say \(k_{j}^{\prime}\), and begin to expand it inward into \(C_{\ell}\), ensuring that \(A_{j}^{\prime}\) and \(A_{j+1}^{\prime}\) remain on the circle, until it encounters a point \(X \in P\). We will show that \(X\) is either one of the vertices of \(C_{\ell}\) or \(X\) lies in the interior of \(C_{\ell}\).
Indeed, suppose the contrary, i.e., the circle \(k^{\prime}\) encounters a point \(X \in P\) that is neither a vertex of \(C_{\ell}\), nor inside this contour. Observe that \(X\) is not in the interior of any of the circles \(k_{i}^{\prime}, i=1,2, \ldots, p\), 2,...,p, because those contain no points of \(P\). Let us denote for brevity \(A:=A_{i}, B:=A_{i+1}\). Let \(P_{\ell}\) be the polygon whhose contour is \(C_{\ell}\), and \(D^{\prime}\) be the disk whose contour is \(k^{\prime}\). Since \(D^{\prime}\) contains the point \(X\) which is outside \(C_{\ell}\) and it does not contain any vertex of \(C_{\ell}\), then \(D^{\prime} \backslash P_{\ell}\) consists of segments cut from \(D^{\prime}\) by some edges of \(C_{\ell}\). Therefore \(X\) is in some of these segments. The following two cases are possible.
1) The circle \(k^{\prime}\) intersects an edge of the contour \(C_{\ell}\) adjacent to \(A B\), say \(B C\), at a point internal to \(B C\), and \(X\) lies on the arc of \(k^{\prime}\) that lies in the half-plane defined by the line \(B C\) which does not contain the point \(A\).
However, if \(k^{\prime}\) intersects the chord \(B C\) of \(k_{j}^{\prime}\) at an interior point \(D\), then the \(\operatorname{arc} \overparen{B D}\) of \(k^{\prime}\), that contains \(X\) lies inside the corresponding circle \(k_{j}^{\prime}\) passing through \(B\) and \(C\) (fig. 4). That is, \(X\) is in the interior of \(k_{j}^{\prime}\), a contradiction.
2) The circle \(k^{\prime}\) intersects an edge \(C D\) of the contour \(C_{\ell}\), which is not adjacent to \(A B\), at two points \(E, F\) interior to \(C D\), and \(X\) lies on the arc of \(k^{\prime}\) that is in the half-plane defined by the line \(C D\) that does not contain the points \(A\) and \(B\).
However, if \(k^{\prime}\) intersects the chord \(C D\) of \(k_{j}^{\prime}\) at interior points \(E\) and \(F\), then the \(\operatorname{arc} \overparen{E F}\) of \(k^{\prime}\) that contains \(X\) lies inside the corresponding circle \(k_{j}^{\prime}\) passing through \(C\) and \(D\) (fig. 5). Therefore, \(X\) is in the interior of \(k_{j}^{\prime}\), contradiction.
Figure 5
In both cases we came to a contradiction. So, we established that \(X\) is either a vertex of \(C_{\ell}\), or \(X\) lies in the interior of \(C_{\ell}\). Further, we add the triangle \(A_{j}^{\prime} A_{j+1}^{\prime} X\) to the triangulation and, similarly to the first step, we define the new contour \(C_{\ell+1}\).
It is important to note that at each step, the triangulation is completely constructed outside the current contour, and we shrink the contour by adding a new triangle inward. In this way, we construct a triangulation that satisfies the Delaunay property. □
Uniqueness. If the points in the set \(P\) are in general position (no three points are collinear and no four points lie on the same circle), there exists a unique Delaunay triangulation for \(P\).
Proof. Suppose there are two distinct Delaunay triangulations \(T\) and \(T^{\prime}\). The edges of the convex hull \(C_{0}\) of \(P\) belong to both triangulations. For each edge \(e \in C_{0}\), let \(\Delta_{e}\) and \(\Delta_{e}^{\prime}\) denote the triangles in \(T\) and \(T^{\prime}\), respectively, whose side is \(e\).
If \(\Delta_{e}=\Delta_{e}^{\prime}\) for all \(e \in C_{0}\), we denote the new contour inward from these triangles as \(C_{1}\) and continue the procedure.
Let \(C_{j}\) be the first contour for which there exists an edge \(e \in C_{j}\) such that \(\Delta_{e} \neq \Delta_{e}^{\prime}\). Let \(e=A B\) and \(\Delta_{e}=\triangle A B C, \Delta_{e}^{\prime}=\triangle A B C^{\prime}\). Note that \(C\) and \(C^{\prime}\) lie in the same half-plane of \(A B\). Since no four points of \(P\) lie on the same circle, we have \(\angle A C B \neq \angle A C^{\prime} B\). Suppose for the sake of clarity
Property 1. The points \(A, B \in P\) are connected in the Delaunay triangulation for the set \(P\) of points in the general position, if and only if there exists a circle through these points that does not contain any points of \(P\) in its interior.
Proof. First, suppose that \(A B\) is an edge in the Delaunay triangulation \(T\). Let \(\triangle A B C \in T\). Then the circle circumscribed around \(\triangle A B C \in T\) does not contain any points of \(P\) in its interior.
Now, suppose that there is a circle \(k\) passing through \(A, B\) that does not contain any point of \(P\) in its interior. There exists a point \(C \in P\), with \(C \neq A, B\), such that \(C \in k\). If this is not the case, we can slightly adjust \(k\) so that this condition holds. We will prove that \(A B\) is an edge in \(T\). Assume the contrary. If neither segment \(A C\) nor \(B C\) is an edge in \(T\), then there will be a point of \(P\) inside \(\triangle A B C\), which is a contradiction.
Therefore, at least one of the two segments, for instance, \(A C\), must be an edge in \(T\). Then there is a triangle \(\triangle A C X \in T\), where \(X\) and \(B\) lie on the same side of the half-plane defined by \(A C\). But then either \(X\) lies inside the circle circumscribed around \(\triangle A C B\), or \(B\) lies inside the circle circumscribed around \(\triangle A C X\). In both cases, we obtain a contradiction.□
Property 1’. (Equivalent formulation) The points \(A, B \in P\) are connected in the Delaunay triangulation for the set \(P\) if and only if there exists a circle through these points that contain no other points of \(P\) either on it or in its interior.
Indeed, if the points of \(P\) are in general position and there is a circle \(k\) that does not contain any points of \(P\) in its interior, then there is at most one point \(X \in P\) lying on \(k\). In this case, we can slightly adjust the circle \(k\) so that it contains only the points \(A\) and \(B\).
Corollary. From the proven property, it follows that if the vertices \(X, Y \in\) \(P\) are not connected in the Delaunay triangulation, then any circle passing through \(X\) and \(Y\) contains a point of \(P\) in its interior.
Property 2. The Delaunay triangulation of an even number of points has a perfect matching.
This non-obvious fact was proven in (Dillencourt 1990). A short proof can be found in (Biniaz 2019). These two properties are sufficient for the applications that follow, but for completeness, we will briefly review some other interesting facts.
3. Some other facts about Delaunay triangulation
Let us mention some other methods for constructing Delaunay triangulation. One of them goes to the 3-dimensional space. Given a set of \(n\) points on the plane with coordinates \(\left(x_{i}, y_{i}\right), i=1,2, \ldots, n\), 2,...,n, we map each point (\(x_{i}, y_{i}\) ) to a point \(\left(x_{i}, y_{i}, z_{i}\right)\), where \(z_{i}=x_{i}^{2}+y_{i}^{2}\). These points lie on a 3-dimensional paraboloid. The projection of their 3-dimensional convex hull is exactly the Delaunay triangulation of the given set of points.
Another algorithm, known as the flip algorithm, starts from an arbitrary triangulation and successively improves it. Let \(A B C\) and \(A B D\) be two adjacent triangles in the current triangulation. If \(D\) lies inside the circumference of \(\triangle A B C\) (fig. 6) then we delete \(A B\) and draw \(C D\) (we flip the edge \(A B\) into \(C D)\).
Figure 6
In the new triangulation, neither \(B\) lies inside the circumference of \(\triangle A C D\) nor \(A\) lies inside the circumference of \(\triangle B C D\). It easily follows that the minimum angle of the two triangles \(A B C\) and \(A B D\) in the first triangulation is less than the minimum angle of the triangles \(A C D\) and \(B C D\) in the second triangulation. We arrange in ascending order all the angles of the triangles that participate in the current triangulation. We get a sequence of \(3 m\) angles, where \(m\) is the number of triangles. This sequence increases (lexicographically) in each next step, so the process of flipping terminates, and no flipping is possible in the final triangulation. It can be proven, although it’s not obvious, that this is exactly the Delaunay triangulation. This implies the following property.
• Delaunay triangulation maximizes the minimum angle. Compared to any other triangulation of the points, the smallest angle in the Delaunay triangulation is at least as large as the smallest angle in any other.
For a set \(P\) of points in general position, consider the nearest neighbour graph. That is, for each point \(x \in P\) we connect it to the closest among the other points in \(P\) (with respect to the Euclidean distance). It may happen that there are multiple nearest points.
• The nearest-neighbour graph is a subgraph of the Delaunay Indeed, let \(y \in P\) be the closest point to \(x \in P\). Construct a circle with diameter \(x y\). There is no other point of \(P\) in the interior of this circle, because otherwise \(y\) would not be the closest point to \(x\). By Property \(1, x y\) is an edge in Delaunay triangulation.
The next fact shows that going from one vertex to another via the edges of Delaunay triangulation, instead of using the straight line between them, is not too slow.
• Delaunay triangulation is a geometric spanner: The shortest path bet two vertices, along Delaunay edges, is no longer than 1.998 times the Euclidean distance between them (XIA 2013).
4. Applications
Problem 1. (Mikl´os Schweitzer 2002, problem 8). Prove that there exists an absolute constant \(c\) such that any set \(H\) of \(n\) points in the plane in general position can be coloured with \(c \cdot \log n\) c colours in such a way that any disk of the plane containing at least one point of \(H\) intersects some colour class of \(H\) in exactly one point.
Solution. (Grozev 2024) An algorithm for colouring the points in \(H\) is as follows. Initially, we set \(P:=H\), and then repeat the following procedure.
Procedure. Construct a Delaunay triangulation for the points in \(P\). Let the resulting planar graph be denoted by \(G(P)\). Since this is a planar graph, its vertices can be colored with 5 colours, with no two connected vertices having the same color. There is a color that is used in at least \(|P| / 5\) of the vertices of \(G\). Let the set of these vertices be denoted by \(P^{\prime}\). Clearly, there are no points in \(P^{\prime}\) connected by an edge. Color all points in \(P^{\prime}\) with a new color that has not been used yet. Set \(P:=P \backslash P^{\prime}\). Repeat the procedure until \(P=\emptyset\).
Let \(D\) be an arbitrary disk containing at least one point of \(H\). We will prove that there is a point in \(D\) colored with a unique color. Let’s focus on the coloring algorithm. We need to show that there is exactly one uncolored point in \(D\) just before it is colored. This will mean that this point is uniquely colored with respect to the other points in \(D\). Assume on the contrary that at some step a set of more than one point \(P^{\prime} \subset H, P^{\prime} \subset D\) gets colored and no uncolored point remains in \(D\). Let \(P\) denotes the set of all uncolored points in \(H\) before this step. Thus, \(P^{\prime} \subset P\) and \(\left(P \backslash P^{\prime}\right) \cap D=\emptyset\). It is easy to see that we can construct a disk \(D^{\prime} \subset D\), whose interior contains no points of \(P^{\prime}\), but there are at least two points of \(P^{\prime}\) on its boundary (fig. 6).
Indeed, let \(O\) be the center and \(R\) the radius of \(D\). Let \(0 \lt r \leq R\) be the smallest number such that the disk \(D^{\prime \prime}\) with center \(O\) and radius \(r\) contains at least two points of \(P^{\prime}\). Clearly, there is at least one point of \(P^{\prime}\) on the boundary of \(D^{\prime \prime}\). There are two possibilities:
Figure 7
1) There are no points of \(P^{\prime}\) in the interior of \(D^{\prime \prime}\);
2) There is exactly one point of \(P^{\prime}\) in the interior of \(D^{\prime \prime}\).
In the first case, we can take \(D^{\prime}:=D^{\prime \prime}\).
Let’s now consider the second case. Let \(X \in P^{\prime}\) be inside \(D^{\prime \prime}\), and \(A \in P^{\prime}\) be on its boundary. Construct the disk \(D^{\prime}\), homothetic to \(D^{\prime \prime}\) with center at point \(A\), so that \(X\) lies on the boundary of \(D^{\prime}\). It is clear that there are no points of \(P^{\prime}\) in the interior of \(D^{\prime}\), and exactly two points of \(P^{\prime}\) on its boundary \(-A\) and \(X\) (fig. 7).
Thus, we have constructed a disk \(D^{\prime} \subset D\) that contains no points of \(P^{\prime}\) in its interior, but has two or three such points on its boundary; let’s denote two of them by \(X\) and \(Y\). It is clear that \(\left(P \backslash P^{\prime}\right) \cap D^{\prime}=\emptyset\), since the points of \(P \backslash P^{\prime}\) lie outside the disk \(D\). According to Property 1, \(X\) and \(Y\) are connected by an edge in the Delaunay triangulation for the points in \(P\), which contradicts the algorithm from the procedure.
It remains to estimate the number of colors used. At each step, we color at least \(|P| / 5\) points of the set \(P\) of uncolored points. This means that the remaining uncolored points are at most \(\tfrac{4}{5}|P|\). Therefore, we will finish in at most \(\log _{5 / 4} n \lt 4 \log _{2} n\) steps, which is the maximum possible number of colors used.□
Problem 2. (239 MO 2024) Given \(2 n\) points in the plane, no three of which are collinear and no four of which lie on the same circle, prove that it is possible to arrange \(n\) disks such that each disk covers exactly two of the given points.
Solution. Let \(P\) denotes the set of the given points. We construct the Delaunay triangulation for \(P\) and let \(G\) be the corresponding planar graph. According to Property 2, there is a perfect matching in \(G\), i.e., we can partition \(P\) into pairs \(u_{i}, v_{i}, i=1,2, \ldots, n\), such that \(u_{i} v_{i}\) is an edge in \(G\). For each \(1 \leq i \leq n\), let \(D_{i}\) be the circumcircle of the triangle from the triangulation with side \(u_{i} v_{i}\) (if there are two such triangles with side \(u_{i} v_{i}\), we choose one). Note that \(D_{i}\) contains exactly three points of \(P\), namely \(u_{i}, v_{i}\), and one more point. It is clear that we can slightly modify \(D_{i}\) so that it contains only \(u_{i}\) and \(v_{i}\) (because the given points are in general position). Let the new disk be denoted as \(D_{i}^{\prime}\), for \(1 \leq i \leq n\). These are the desired disks.
Problem 3. (ELMO Shortlist 2024/C1) Let \(n \geq 3\) be an integer, and let \(S\) be a set of \(n\) distinct points in the plane. Call an unordered pair of distinct points \(A, B\) tasty if there exists a circle passing through \(A\) and \(B\) but not passing through or containing any other point in \(S\). Find the maximum number of tasty pairs over all possible sets \(S\) of \(n\) points.
Solution. Note that if \(\{A, B\}\) is a friendly pair, then according to Property \(1, A B\) is an edge in the Delaunay triangulation for \(S\). Therefore, the number of friendly pairs does not exceed the number of edges in the triangulation of \(n\) points, i.e., the maximum possible number of edges in a planar graph with \(n\) vertices. It is well known that this number is \(3 n-6\), and it is attained in a triangulation whose convex hull is a triangle.
On the other hand, if we take such a configuration of points in general position, then the Delaunay triangulation for them has exactly \(3 n-6\) edges. According to Property 1, for each of these edges, there is a circle that contains it and does not pass through or contain any other points in \(S\). □
REFERENCES
BINIAZ, A., 2020. A Short Proof of the Toughness of Delaunay Triangulations. Proc. of Symposium on Simplicity in Algorithms, pp. 43 – 46, SIAM. doi: 10.1137/1.9781611976014.8
DELAUNAY, B., 1934. Sur la sph`ere vide. A la m´emoire de Georges Vorono¨ı. Извeстия АН СССР. VII серия. Отделение математических и естественных наук, no. 6, pp. 793 – 800.
DILLENCOURT, M.B., 1990. Toughness and Delaunay triangulations. Discrete & Computational Geometry, vol. 6, no. 5, pp. 575 – 602.
GROZEV, D., 2024. A Point of View (Blog).
https://dgrozev.wordpress.com
XIA, GE, 2013. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. on Computing, vol. 42, no. 4, pp. 1620 – 1659.