About one interesting property of Delaunay triangulation

In the process of solving a certain problem, I came across one interesting property Delaunay triangulationswhich I couldn't google, nor could I find any application for it to solve various problems. I'm sure I'm not its discoverer, but at least it's not widely known. So I decided to write an article about it.

Property: If some segment AB is not included in the Delaunay triangulation, then there is a path from A to B along segments from the triangulation such that all segments there are no longer than |AB|. In the picture above, the missing segment is shown in red, and the path is shown in green.

Later in the article I will give an example of its use in problems, as well as its formal proof.

If you know a more beautiful proof of this property, or you have seen it somewhere, please share it in the comments. I will also be grateful if you share other solutions for the problems given in the article or similar problems.

Introduction

First, let me remind you what the Delaunay triangulation is and how it is related to the Voronoi diagram. You can skip this section if you are familiar enough with at least the page in wikipedia.

A Delaunay triangulation is a triangulation for a given set of points S in the plane such that for any triangle, all points in S except the points that are its vertices lie outside the circle circumscribed around the triangle (or at least do not lie inside this circle).

If no 4 or more points of the set S lie on one circle inside which there is no other point from S, then the triangulation is unique. Otherwise, these 4 or more points form a convex polygon in the triangulation, which can be triangulated arbitrarily. But outside these points, the triangulation is still unique.

An important property of triangulation is that it has O(n) edges. This can be proven, for example, using Euler's formula for planar graphs: (1, not 2, because there is also an outer region), after all will count each internal edge twice, and each external edge once. This gives.

Triangulation is closely related to the Voronoi diagram for a set S – it is a partition of the plane such that each region of this partition forms a set of points that are closer to one of the elements of the set S than to any other element of the set.

The Delaunay triangulation and the Voronoi diagram are dual structures: each region or “cell” of the diagram corresponds to a vertex of the Delaunay triangulation. If two cells are adjacent by a side, then there is necessarily a segment in the triangulation between the two corresponding points. If there is a segment in the triangulation, then the two cells are definitely adjacent, at least by the vertex. These two statements are slightly asymmetric, because when more than 3 cells intersect at the same vertex, we get the polygons mentioned above, which can be triangulated arbitrarily. Therefore, it is not a fact that between any two cells adjacent by a vertex there is necessarily a segment in the triangulation. Here is an example from Wikipedia:

The Voronoi diagram is shown in red. The Delaunay triangulation is shown in black.

Tasks

Here I will give several problems that are solved via Delaunay triangulation due to the property found. All these solutions are in O(n log n), because a triangulation, like a diagram, can be constructed in O(n log n), and then something remains to be done only with O(n) segments. A naive solution is usually O(n^2) – by the number of all possible segments, or even worse.

Find the two closest points in a set of points.

Solution: let's construct a Delaunay triangulation and find the minimum segment in it, which will be the answer.
Note: There is another well-known divide-and-conquer solution to this problem. But this problem demonstrates the principle of applying the property found, so I left it.
Proof: Consider the two closest points in the set. If the segment between them is in the triangulation, then it will already find this optimal answer. Otherwise, by property, in the triangulation there is a path of segments not shorter than this segment, but since it is the shortest by definition, then all these segments in the path are of the same length. This means that the algorithm will find some other segment with the same optimal length.
Find the distance between two sets of points.
Solution: Using sorting or a hash table, we check whether 2 points from different sets coincide. Otherwise, we construct a Delaunay triangulation for the combined set of points. We find the minimum segment in the triangulation whose ends are from different sets, and this will be the answer.
Proof: Similar to the previous problem. Consider the two closest points from the sets. If the segment between them is in the triangulation, the algorithm will find this correct answer. Otherwise, there will be a path of segments of the same length or shorter. This path starts in one set and ends in another, which means that one of the segments in it has ends in different sets. This segment will not be longer than the optimal one and the algorithm will consider it, which means it will find the correct answer.
Find the minimum spanning tree on a set of points.
Solution: Let's construct a Delaunay triangulation. Let's find the minimum spanning tree in this graph.
Note: The fact that the Delaunay triangulation contains a minimum spanning tree is mentioned on the Internet, but I have not found a proof, so I am also citing this problem.
Proof: First, let's assume that we are searching for a spanning tree using Kruskal's algorithm in a complete graph with n(n-1)/2 edges. The algorithm obviously works. Now let's assume that when sorting edges of the same length, we first take the edges from the triangulation, and then those that are not included there. The algorithm still works. Now let's show that when considering edges not in the triangulation, the algorithm will always skip them, because the two ends will already be in the same connected component. Indeed, according to the property, it turns out that there is a path between the ends, and all the edges there will already be considered – after all, they are either shorter or of the same length, but from the triangulation, and therefore come earlier in the sorting. This means that the two ends of the edge already belong to the same component. Therefore, edges not from the triangulation can simply be excluded from consideration and the result of the algorithm will not change. So we have constructed a minimum spanning tree in the entire graph, considering only the edges from the triangulation. Now we can forget about the specific algorithm. It doesn't matter how we search for the minimum spanning tree, we've already proven that it exists.
There are N radio towers on a plane. Two towers can exchange messages if they are no more than R apart. Determine whether the network of all towers is connected.
Solution: Let's construct a Delaunay triangulation, leaving only those edges that are no longer than R. Let's check that the graph is connected.
Proof: Consider some edge of the complete graph AB, no longer than R. If it is included in the triangulation, then the two ends will be in the same component. If it is not included, then the triangulation will include a path of edges no longer than |AB|, and since |AB| is no longer than R, then all these edges will also be no longer than R. It turns out that A and B will still be in the same connectivity component. Therefore, the graph of edges only in the triangulation has the same connectivity components as the complete graph.
There are N radio towers on a plane. Two towers can exchange messages if they are no more than R apart. Find the minimum value of R at which the network of all towers is connected.
Solution: Let's construct a Delaunay triangulation. We'll add edges from there in order of increasing length until the graph becomes connected. The length of the last edge added is the answer.
Proof: In fact, this problem is similar to the 3rd problem about the spanning tree. After all, the minimum spanning tree minimizes not only the sum of the lengths of the edges, but also the maximum edge in the tree. This is obvious at least from Kruskal's algorithm.

Proof of the property

Let's assume that the segment AB is not included in the triangulation. Let's consider the Voronoi diagram. The segment intersects some cells. Let's designate the centers of these cells as (in the order of intersection of the segment from A to B).

Obviously, ,

Note that the segments $P_iP_{i+1}$ are included in the triangulation because they are the centers of adjacent Voronoi cells.

Let us first assume that the segment AB does not intersect any vertex of the Voronoi diagram (a point where 3 or more cells are adjacent). Let us designate the points at which AB intersects the boundary between And $P_{i+1}$ How .

Because the lies on the cell boundary for the point That $|P_i T_i| \le |A T_i|$ because this cell is a geometric location of points that are closer to than to any other point from S, including A. Moreover, this inequality is in force, even for i=1, because if That And – this is the same segment.

Similarly for the cell $P_{i+1}$ we get that $|P_{i+1}T_i| \le |BT_i|$ .

By the triangle inequality we obtain $|P_iP_{i+1}| \le |P_iTi|+|P_{i+1}T_i|$
We apply the two inequalities obtained earlier: $|P_iP_{i+1}| \le |AT_i| + |BT_i|$
Note that here on the right there are two pieces that make up the segment AB, and here we have the desired inequality: $|P_iP_{i+1}| \le |AB|$

It only remains to deal with the case when a segment passes through a vertex in the Voronoi diagram. Here we can assume that the segment passes in a row through all the cells it touches in a counterclockwise order. Here is an explanatory picture:

We will get a new list where every 2 adjacent points will be the centers of adjacent cells on the side, which means there will be a segment between them in the triangulation. As a point we will take the same vertex of the diagram through which AB passes. In all the calculations above about the lengths of the segments, it was only important to us that lies on the cell boundary: either on the side or at the top.

So we have proved that the triangulation contains a path of segments, each of which does not exceed |AB|.

Perhaps it would be worthwhile to prove more formally that the segment AB intersects a finite set of cells, each once in a uniquely determined order, but this all follows from the convexity of the cells of the Voronoi diagram and seemed to me to be an unnecessary formalism.

Another controversial point is what will happen if the segment AB passes through some center of the cell of the Voronoi diagram. This does not spoil anything, it’s just that this center will be some kind of regular and the path from the segments in the triangulation will simply touch the segment AB at this vertex somewhere.

It is also possible to prove it exclusively through the Delaunay triangulation, but it seems to be a more tedious proof with a bunch of geometric calculations. I didn't even finish it.