Next: Safe Violation Up: Elimination of Cyclic Violation Dependency Previous: Elimination of Cyclic Violation Dependency

### Point Perturbation

The point perturbation eliminates the violation by moving the point violating a constraining facet . This means that the point is shifted out of the sphere circumscribed to the facet. The shifted position of the point is accepted only if the following criteria are satisfied

• the point is not violating ,
• no new violation is created,
• the point is not co-planar with any of the constraining facets whose empty-circumsphere property it is violating,
• the constraining facets incident to the point are not intersected by any other constraining facet,
• the constraining facets incident to the point are not co-planar with any of points violating their empty-circumsphere property, and
• the shift (total shift if the point is not perturbed for the first time) does not exceed a threshold value.

In the current implementation, the initial position of the perturbed point is calculated by shifting it perpendicularly to the plane of (rather out of the domain to prevent creation of slivers). This initial position is then modified to prevent the point to be located in the plane of any of the constraining facets violated by the point. This position is further iteratively adjusted using additional shifting radial to the circumsphere of any constraining facet (including ) which empty-circumsphere criterion is violated by the current point position. This process is schematically depicted on a 2D example in Figure 6a. Note however, that in 2D, a point cannot violate constraining edge and be simultaneously co-linear with it, unless the edge is crossing the point.

If the final position of the perturbed point fails to comply with any of the above requirements the whole process is repeated once again, this time however, with the initial location obtained by a shift radial to the smallest sphere circumscribed to (Figure 6b). Should this attempt fail again, the first requirement is sacrificed and the point is perturbed only to prevent its co-planarity with all constraining facets (including ) violated by it. If this also fails, perturbation is not accomplished at all. If the perturbation is performed, the dependency graph as well as the parallelepiped used for the construction of the initial Delaunay triangulation are updated appropriately.

In order to make the perturbation process efficient, the circumspheres of all constraining facets are precomputed (and updated after successful perturbation). Together with the list of points violating each constraining facet, also a list of points that could violate it, if the point is perturbed not more than the limit value (currently set to one tenth of the local element size), is stored. The intersection of two constraining facets is examined only if circumsphere of one of the facets is violated by at least one of vertices of the other facet.

Next: Safe Violation Up: Elimination of Cyclic Violation Dependency Previous: Elimination of Cyclic Violation Dependency

Daniel Rypl
2005-11-06