Introduction to the Bowyer-Watson Algorithm

The Bowyer-Watson algorithm is a widely-used method for constructing Delaunay triangulations. The process begins with a "super triangle," a single, large triangle that encompasses all the points in a given set. As points are added, the algorithm removes triangles that violate the Delaunay property—specifically, those whose circumcircles contain the new point—and replaces them with new triangles. This article will delve into the intricacies of managing the "holes" formed when removing these triangles, particularly those involving vertices of the super triangle.

Fundamentals of Delaunay Triangulation

Delaunay triangulation involves connecting a set of points in such a way that no point is inside the circumcircle of any triangle. This maximizes the minimum angle of the triangles, avoiding skinny triangles and resulting in a more natural shape.

The Super Triangle

The algorithm starts with a super triangle that contains all the given points in a dataset. This super triangle is fundamental because:

• Initialization: It serves as the starting point for the algorithm.
• Boundaries: It helps define the boundary for edge connections as points are added.

Generating a Super Triangle

The vertices of the super triangle are often placed at extreme coordinates, far enough from the datasets to ensure encapsulation. For a set of 2D points, the super triangle can be constructed using:

1. Identify extremes: Calculate the bounding box of the data points with a margin to ensure encapsulation.
2. Form triangle: Place vertices at the bounding box corners or points extended from these corners.

Bowyer-Watson Algorithm Steps

1. Initialization: Start with the super triangle covering all points.
2. Insert Points:
   • For each new point, identify all triangles whose circumcircle contains this point.
   • Remove these triangles, creating a hole.
3. Fill the Hole:
   • Form new triangles by connecting the point to the edges of the hole.
4. Repeat: Continue inserting points until all are included in the triangulation.

Filling "Holes" in Triangulation

When you remove triangles that include the new point inside their circumcircle, you essentially create a "hole." This section will describe the process of filling these holes, focusing on handling the super triangle vertices.

Challenges with Super Triangle Vertices

The vertices of the super triangle are not part of the actual data set and must eventually be removed. Thus, triangles associated with these vertices also need to be replaced carefully:

1. Identify Boundary Edges: When removing a triangle, identify the edges but consider only those not forming part of the super triangle.
2. Connect: Link the new point to the identified boundary edges, ensuring none of the resulting triangles include super triangle vertices.
3. Removal: After all data points are processed, remove triangles associated with super triangle vertices, leaving the valid Delaunay triangulation.

Example

Consider a dataset of four points within a super triangle:

• Initial Setup:
  • Super triangle vertices: $A$, $B$, $C$
  • Data points: $P1$, $P2$, $P3$, $P4$
• Step-by-step:
  1. Add $P1$, check triangles $\Delta ABC$, update.
  2. Add $P2$, check and remove overlapping circumcircle with $\Delta ABC$, add $\Delta ABP1$, $\Delta ACP1$, $\Delta BCP1$, and update.
  3. Continue with $P3$ and $P4$, always forming new triangles using boundary edges.
  4. Finally, remove triangles associated with $A$, $B$, and $C$.

Filling the Final "Hole"

As the algorithm progresses, remaining triangles involving super triangle vertices are inherently removed. This maintains the Delaunay criteria by ensuring all triangles are part solely of the data points.

Key Points Summary

Extensions: Handling Degenerate Cases

In practice, various complications can arise, such as:

• Collinear Points: Special attention is required to handle situations where points are collinear.
• Numerical Precision: Small numerical errors can lead to difficulties in checking circumcircle properties.

In these cases, robust algorithms and data structures, such as the use of floating-point arithmetic with precision control, can help ensure the algorithm's correctness and efficiency.

Conclusion

The Bowyer-Watson algorithm is an efficient method for constructing Delaunay triangulations, particularly helpful in applications such as finite element methods, meshing, and geographic information systems. By managing the initial super triangle and correctly handling the removal and addition of triangles, the algorithm ensures a correct and optimized boundary for any given dataset.