Safe Violation

The violation of empty-circumsphere property of a constraining facet is classified as safe if points violating are inserted before the vertices of and

- the facet appears in the Delaunay triangulation yet or
- the presence of the facet in the Delaunay triangulation can be recovered by a simple topological transformation immediately after its vertices are inserted.

The former case is verified using the empty-sphere property applied to the sphere circumscribed to the simplex formed by the constraining facet and point violating and yielding the largest circumsphere (Figure 7a). The fulfillment of this criterion implies that all the points violating are located on the same side of . Note that even if the empty-circumsphere property is not satisfied due to points , the violation of can be declared as safe if neither from points is inserted before point (Figure 7b). This alternative is currently not used as it introduces new dependencies of on in the dependency graph, possibly producing new cyclic dependencies.

A more refined version of the above verification (not relevant in 2D, however) can be applied if there is a guarantee that an -dimensional simplex bounding appears in the Delaunay mesh. This may be checked using the empty-sphere property applied to the smallest -dimensional sphere circumscribed to . But even if this empty-circumsphere condition is not fulfilled, will be present in the Delaunay triangulation if it is bounding another constraining facet, which is either not violated at all, or is violated safely, or its violation is not part of any cyclic dependence in the dependency graph. Then the empty-sphere property related to the sphere circumscribed to can be broken by a point unless this point is located in the halfspace defined by the plane passing through and and by point forming with constraining facet . An example of such a case is shown in Figure 8. This refined version is especially useful when handling mutual cyclic dependence between two points which are incident to two different adjacent constraining facets sharing . The cyclic violation in such a case does not preclude the appearance of in the Delaunay triangulation and the refined verification of safe violation can be harmlessly applied.

In the latter case, the basic assumption to perform a simple topological transformation is the appearance of the boundary of constraining facet in the Delaunay triangulation. This is verified for each -dimensional simplex bounding using the same approach as explained in the preceding paragraph. In 3D problems, a topological transformation is currently considered simple only if the constraining face (missing in the Delaunay triangulation) is intersected just by a single edge. In such a case, the missing face is recovered simply by the 3-to-2 transformation (Figure 9). Note that in 2D, is actually a point from , thus always appears in the Delaunay triangulation. To ensure that missing constraining facet is not intersected by more than one edge, the following conditions have to be satisfied

- constraining facet is violated either by a single point or by two points on opposite sides of ,
- in the sphere circumscribed to the simplex formed by and any of points violating there is just a single point (this is the other point if is violated by two points),
- there must be no point inside the sphere circumscribed to the simplex formed by , , and and simultaneously in the halfspace defined by the plane passing through and and by point forming with constraining facet (the halfspace restriction is irrelevant in 2D).

Note that the parallelepiped for the initial Delaunay triangulation should be updated (properly increased) each time any of its corners (temporarily considered as part of ) would prevent a particular violation to be classified safe.

*Daniel Rypl
2005-11-06*