5.6 Steiner Points and Steiner Triangulation

In the context of a Delaunay Triangulation and other optimal triangulations/tetrahedralizations Steiner points refer to points which are added to the set of vertices of the input PSLG/PLC $I$. The name does not indicate a specific location for the added point. While refinement is quite naturally considered for mesh generation purposes, the addition of Steiner points to a Delaunay Triangulation is a powerful concept in computational geometry which allows quite theoretical investigations. It forms the basis for many provable optimal triangulation algorithms for various quality criteria [16,15,134].

Figure 5.6: Steiner point insertion at the circumcenter, removal of non-Delaunay elements, and triangulation of the resulting cavity.

One of the most important techniques is the insertion of a Steiner point at the circumcenter of a badly shaped element. The element is not necessarily refined itself, because its circumcenter might be located in an adjacent element. In a subsequent step the Delaunay property is restored which ensures the destruction of the undesired element because its circumsphere is not empty. The minimum distance between two points cannot be reduced unproportionally. The circumsphere of a Delaunay element contains no other points, hence the inserted circumcenter cannot lie arbitrarily close to another point. This allows a proof of good grading. The refinement can be bounded by disallowing the insertion of circumcenters for circumspheres smaller than a given limit. Then, the insertion process must terminate, because it runs out of space.

Figure 5.7: Delaunay Triangulation vs. quality improved Steiner Triangulation. The original 130 triangles (94 points) were refined with 128 Steiner points resulting in 376 triangles.

For example in two dimensions a scheme can be devised to guarantee angles between $30^{\circ }$ and $120^{\circ}$ as long as the length of the boundary edges is within a specified range [28]. Figure 5.6 shows an obtuse triangle which is removed by inserting its circumcenter and restoration of the Delaunay property. An example triangulation is shown in Fig. 5.7. The key idea is that a Steiner point at the circumcenter directly affects the shortest edge to circumradius ratio quality measure $Q_{1}$ (3.1).

Figure 5.8: The worst case element with a $30^{\circ }$ angle and minimum edge length $b$. The largest circumcircle has radius $b$.

To see this it is assumed without loss of generality that the minimum distance between two points of the input $I$ is $b$. Steiner points are inserted as long as elements exist with circumradius greater than $b$. The restoration of the Delaunay property after each point insertion is possible with flip operations. Hence, it can be guaranteed due to the Delaunay property that the inserted points are also not closer than $b$ to any other point. Simultaneously it is guaranteed that no circumradius is greater than $b$. Termination is guaranteed because each point defines a disk with radius equal to the minimum distance $b$ in which no other points may be located. All such disks sooner or later cover the entire available space and no more points can be inserted. The resulting edge length ranges between the minimum distance $b$ and the maximum $2b$ which is possible for the maximum circumcircle with radius $b$. Hence, the worst (minimal) quality is $Q_{1} = \frac{l_{\min}}{R} = \frac{b}{b} = 1$ (Fig. 5.8). Because of (3.7) the minimum angle is $\alpha = \arcsin \frac{b}{2b} = 30^{\circ}$.

Figure 5.9: A naive approach where the bisection of boundary edges and the insertion of circumcenters runs into an endless loop. The small angle which causes the insertion of a Steiner point at the center of the dotted circumcircle is shaded. A better solution can be obtained and is shown in the bottom left corner.

An analysis which includes the boundary is more complex [135,29]. Certain restrictions have to be applied to the edges and facets of $I$. As already mentioned the edge lengths must be within a certain range or the edges must form angles of e.g. no less than $90^{\circ}$. Naturally, edges of the input $I$ can form a sharp angle which is forced into the triangulation and which cannot be resolved. If a Steiner point lies outside of the domain defined by $I$, it cannot be inserted. Figure 5.9 shows an obtuse element of which the longest edge is a boundary edge and the circumcenter is outside. An intuitive approach to bisect the longest edge to destroy the obtuse angle combined with a minimum angle criterion enforced through Steiner point insertion at circumcenters may run into an endless loop (Fig. 5.9). Alternately the boundary edge is further bisected and a Steiner point added at the circumcenter of the new element. The boundary edge can never be flipped and the angle never improves. A solution is to check whether or not a Steiner point candidate inflicts the smallest sphere criterion of a boundary edge. As can be seen in Fig. 5.9 the inserted circumcenters are always located inside of the smallest circle passing through the two vertices of the boundary edge. In such cases the Steiner point candidate should be discarded and the boundary edge should be instead refined itself. Generally, a Steiner point insertion algorithm must stop the attempt to resolve bad angles in impossible situations due to special constellations of the edges and facets of $I$, rather then to cause excessive refinement. Restrictions on $I$ are not acceptable for practical implementations.

A detailed comparison of Steiner Triangulation algorithms is given in [162]. Depending on how the boundary is handled different angle bounds can be achieved [135,28,29]. Often it is experienced that a theoretical minimum angle bound of e.g. $20^{\circ}$ can be increased in practice up to $30^{\circ }$. A Steiner Triangulation with circumcenters is just as powerful in three dimensions to improve the shortest edge to circumradius quality criterion $Q_{1}$ [30,37]. However, as was pointed out in Section 3.1 sliver elements are not captured by $Q_{1}$ and are not removed by inserting circumcenters as Steiner points. A three-dimensional method which promises to avoid all badly shaped elements and which is based on a two-dimensional approach with Steiner points [16] is proposed in [109].