2. Concept

Delaunay Triangulation

The most commonly used triangulation in practice is Delaunay triangulation, which is a special kind of triangulation that meet the following properties:

Delaunay triangulation is unique , in Delaunay triangulation there will be no other points within the circumcircle of any triangle

A triangle is formed by the three nearest points, and each line segment does not intersect.
No matter where the area starts from, the final result will be consistent.

If the diagonals of the convex quadrilateral formed by any two adjacent triangles are interchangeable, then the smallest angle among the six internal                 angles of the two triangles will not become larger.

If the smallest angle of each triangle in the triangulation is arranged in ascending order, the arrangement of the Delaunay triangulation will get the largest value.

Adding, deleting, or moving a vertex will only affect the adjacent triangle.
The outermost boundary of the triangular mesh forms a convex polygon shell.

Many algorithms for computing Delaunay triangulations rely on fast operations for detecting when a point is within a triangle’s circumcircle and an    efficient data structure for storing triangles and edges.

Among these algorithms, the point-by-point insertion algorithm is relatively simple and easy to understand.

The Isometry Between Binary Trees and Polygon Triangulations

How, you may ask, can we represent a binary tree with a polygon? The process involves triangulation, where we recursively divide the polygon into triangles. A triangle represents a node in the binary tree, and a shared edge between two triangles indicates that the two corresponding nodes in the tree are adjacent.

Importantly, the triangulation process only considers the tree’s shape rather than considering any keys that may be stored in the nodes. To illustrate this, we relabel each node with its place in the symmetric order (i.e., the order generated by an inorder traversal of the binary tree). Supposing you start with an m-node binary tree, relabel the nodes as follows:

Now, draw a convex (m+2)-gon. Designate an arbitrary edge to be the root edge, and label the remaining vertices of the polygon that are not on the root edge with the numbers one through m. As a convention, we’ll go counterclockwise.

Create a triangle by drawing line segments from the root edge’s endpoints to the vertex corresponding to the root node of the tree. We’ll refer to these segments as diagonals. This triangle, called the root triangle, represents the root node.

Notice that the root triangle separates the vertices corresponding to the left subtree (1 through 4, in the figure above) from the vertices corresponding to the right subtree (6 and 7). Drawing the root triangle, then, decomposes the polygon into (at most) three polygons: the root triangle itself, plus a polygon for each of the two sub-trees of the root.

To complete the triangulation, recursively triangulate each of these two polygons according to the process described above, using the two newly-drawn diagonals as the root edges of their respective polygons. In the figure below, we start with the left subtree, connecting the new root edge in the leftmost polygon to the vertex (2) corresponding to the root node of the left subtree. Similarly, these diagonals act as root edges for the newly created polygons, which correspond to the sub-trees of node 2. We repeat the same procedure to triangulate the entire left subtree; at this point we just need to draw one additional diagonal to complete the triangle that corresponds to node 3. Next, we follow the same procedure for the right subtree.

A binary tree has only one possible triangulation because each triangle in the triangulation is uniquely determined by two things: 1) a diagonal that has already been drawn as part of the triangulation (or the root edge as a special case) and 2) the vertex of the polygon corresponding to a particular node.

In addition, one convenient property of the isometry is that two triangles are adjacent (share an edge) if and only if their corresponding nodes in the tree are adjacent (have a parent-child relationship). This property will be useful later on.

To more clearly see which triangles correspond to which nodes, it may be helpful to overlay the tree on top of its triangulation, shown below. Notice how it’s still possible to discern the original tree structure when looking at its triangulation.