Next: Point Perturbation Up: A Priori Boundary Recovery Previous: Violation Dependency Graph

Elimination of Cyclic Violation Dependency

The elimination of the cyclic violation dependency is crucial for the successful accomplishment of the dependency driven point insertion process. In the present study, three basic actions are taken to remove from the dependency graph at least one dependency connection in each cycle. These are

The point perturbation attempts to remove a violation, while not introducing any new one. The classification of a particular violation as safe does not physically remove it but allows its elimination from the violation dependency graph, as the violating point can be inserted before the violated facet without the risk that the facet does not appear in the triangulation or with the guarantee that it can be easily recovered by simple topological transformation immediately after all its vertices are inserted. The formation of a new simplex removes from the set of constraining facets those being used to form the new simplex (assuming that each constraining facet corresponds to the outer boundary of the domain to be discretized) and simultaneously it inserts in that set the newly created facets. The removal of the facet also effectively removes all the violations of its empty-circumsphere property. However, introduction of new constraining facets requires verification of their appearance in the Delaunay triangulation and update of the dependency graph.

Since the point perturbation can make safe violations again unsafe, the perturbation is always performed before classifying the violations as safe. The creation of a new simplex is applied as the last resort. If a new point is created to form the new simplex, as well as if new cyclic dependencies are introduced, all safe violations are declared as unsafe and the above three steps are repeated until all cyclic dependencies are eliminated.


Next: Point Perturbation Up: A Priori Boundary Recovery Previous: Violation Dependency Graph

Daniel Rypl