Delaunay triangulation

In computational geometry, a Delaunay triangulation or Delone triangulation helps organize a set of points in a plane by dividing the space into triangles. The key idea is that each triangle’s circumcircles—the circles that pass through all three corners of the triangle—do not contain any other points from the set inside them. This rule ensures that the triangles have healthy angles, avoiding very skinny or “sliver” shapes, which are sliver triangles.

The method is named after Boris Delaunay, who introduced it in 1934. Delaunay triangulation is especially useful in computer graphics, mapping, and many types of scientific simulations because it creates well-shaped triangles that make calculations more accurate and efficient.

Sometimes, special cases can happen. For example, if all the points lie on a straight line, there is no proper triangulation. And if points sit on the same circle, like the corners of a rectangle, there might be more than one correct way to draw the triangles. The concept can also be expanded into three dimensions and beyond by using spheres instead of circles, though it becomes more complex in those cases.

Relationship with the Voronoi diagram

The Delaunay triangulation is closely linked to the Voronoi diagram. When you connect the centers of the circumcircles of the triangles in a Delaunay triangulation, you create a Voronoi diagram. In simple terms, the centers of these circles become the points in the Voronoi diagram.

There are some special cases where this relationship can be tricky. For example, if points are lined up or if points lie exactly on a circle, the patterns can become unclear. But in most cases, the two diagrams help show how points are arranged and related to each other.

d-dimensional Delaunay

A Delaunay triangulation is a special way to connect points in space to make triangles or other shapes. For any set of points, it makes sure that no point is inside the circle (or sphere in higher dimensions) that passes through the points of each triangle. This helps create shapes that are well spread out and avoid very thin triangles.

To find this triangulation in higher dimensions, we can turn the problem into finding the shape of a group of points in one higher dimension. By adding an extra measurement to each point, we can use the shape of the outer edge of these points to figure out the triangles in the original space. This method works because the outer shape is unique, leading to a unique set of triangles as well.

Properties

The Delaunay triangulation has some interesting properties. It creates shapes (called simplices) that cover the outer shape (convex hull) of a set of points. In a flat plane, if you know how many points are on the outer edge, you can figure out the maximum number of triangles a triangulation can have.

One key feature of the Delaunay triangulation is that it tries to make the smallest angles in the triangles as large as possible. This helps avoid very thin, "sliver" triangles. Also, for any triangle in this triangulation, the circle that passes through its three points won’t contain any other points inside it. This makes the Delaunay triangulation useful in many applications, like computer graphics and mapping.

Visual Delaunay definition: Flipping

When looking at two triangles that share a side, we can check if they follow the Delaunay rule. If the angles next to the shared side add up to less than or equal to 180 degrees, the triangles are good.

If they don’t follow the rule, we can switch the shared side to make two new triangles that do follow the rule. This switch is called “flipping” and works in more than just two dimensions.

Algorithms

Many ways exist to create Delaunay triangulations, which are special shapes formed from points. One common method involves checking if adding a point makes a triangle follow the Delaunay rule — that no point lies inside the circle surrounding each triangle’s corners.

One simple method starts with any triangle shape and adjusts edges until all triangles meet the Delaunay rule. Another method adds points one by one and adjusts nearby triangles each time. There are also faster methods that split the points into groups, solve each group separately, and then combine the results. All these methods aim to create the best possible triangle shapes from a set of points.

Main article: Bowyer–Watson algorithm

Applications

The Delaunay triangulation is useful in many areas. For example, it helps create models of terrain or objects from a group of points, avoiding very thin triangles. This makes the models look more natural.

It is also used to create meshes for solving physics problems, like how heat spreads or how objects move. These meshes need to be strong and accurate, and Delaunay triangulation helps make sure they are. It can even be used in planning paths for self-driving cars.