Delaunay triangulation

Delaunay triangulation

In computational geometry, a Delaunay triangulation or Delone triangulation helps organize points on a flat surface by dividing the space into triangles. The main idea is that the circles passing through each triangle’s three points do not contain any other points inside them. This rule helps create triangles with good angles, avoiding very thin or “sliver” shapes, which are sliver triangles.

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

Sometimes, special cases can occur. 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 idea can also be used in three dimensions and beyond by using spheres instead of circles, though it becomes more complex.

Relationship with the Voronoi diagram

The Delaunay triangulation is closely linked to the Voronoi diagram. When you connect the centers of the circles around 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 that cover the outer shape of a set of points. In a flat plane, you can find the maximum number of triangles a triangulation can have.

One key feature is that it tries to make the smallest angles in the triangles as large as possible. This helps avoid very thin triangles. Also, for any triangle, 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 two triangles share a side, we can check if they follow a special rule called the Delaunay rule. If the angles next to the shared side add up to 180 degrees or less, the triangles are just right.

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

Algorithms

There are many ways to create Delaunay triangulations, which are special shapes made from points. One common way checks if adding a point keeps a triangle following the Delaunay rule — meaning no point is inside the circle around each triangle’s corners.

A simple method starts with any triangle and changes its sides until all triangles follow the Delaunay rule. Another method adds points one at a time and changes nearby triangles each time. There are also quicker methods that split points into groups, solve each group, and then put the results together. All these methods work to make the best 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 make models of terrain or objects from a group of points. It stops the models from having very thin shapes, so they look more natural.

It is also used to build networks for solving science problems, like how heat moves or how things shift. These networks need to be strong and correct, and Delaunay triangulation helps with that. It can also help plan routes for self-driving cars.