Next: Elimination of Cyclic Violation Dependency Up: A Priori Boundary Recovery Previous: A Priori Boundary Recovery


Violation Dependency Graph

The violation dependency graph is an oriented graph whose nodes are the points from . The connection from point to point (point is dependent on point ) is established only if point is a point violating the empty-circumsphere property of violated facet incident to point . The dependency graph is built at the beginning of the a priori boundary recovery process by verifying the appearance of each constraining facet in the Delaunay triangulation. It is important to realize that the constraining facets could be also violated by the corner points that are used as points of the initial Delaunay triangulation but which are not contained in set . To prevent such a violation, the corner points should be located sufficiently far from the constraining facets. This can be simply achieved by constructing a parallelepiped surrounding the smallest circumspheres of all the constraining facets. The corners of this parallelepiped are then used as the corner points of the initial Delaunay triangulation.

If the graph is not cyclic (there are no closed dependency cycles in the graph), the point insertion process can be commenced starting with an arbitrary point. However if this point is dependent on any other point, that point must be inserted first. Since the graph is not cyclic, this dependency based ordering always exists, even if it may not be unique.

A simple example of 2D sets of points and constraining edges is depicted in Figure 3a. The corresponding violation dependency graph is shown in Figure 3b. One possible point insertion ordering, that can be derived from that dependency graph and which ensures that all constraining edges appear in the resulting constrained Delaunay triangulation, is suggested in Figure 3c.

Unfortunately, the cyclic dependency in the graph is likely to occur. Two simple examples of such a case are sketched in Figures 4a and 5a again for 2D sets of points and constraining edges. It is apparent that the point insertion ordering cannot be established without eliminating certain connections from the dependency graph (Figures 4b and 5b).



Next: Elimination of Cyclic Violation Dependency Up: A Priori Boundary Recovery Previous: A Priori Boundary Recovery

Daniel Rypl
2005-11-06