** Next:** Domain Discretization
**Up:** Elimination of Cyclic Violation Dependency
** Previous:** Safe Violation

###

Simplex Formation

The creation of a new simplex inside the domain is used as the last
resort to get rid of all the violations associated with the
constraining facets used to form the simplex. Assuming that each
constraining facet corresponds to the outer boundary of the domain to
be discretized, once it is used to form , it can be removed from the
set of constraining facets. The new simplex is then temporarily
considered to be out of the domain and its newly created boundary facets
are appended to the set of constraining facets. The dependency graph
is then updated to account for these new facets. Similarly, any existing
point used to form is removed from set if it is not incident
to any constraining facet in . If a new point was established to form
(recall, that the constrained Delaunay triangulation may not exist for
given and ), the point is added to and the dependency graph
is updated. Since any safe violation can generally become again unsafe
after the new point is introduced, there is a strong tendency to use
only existing points, whenever possible, to form . Should this effort
fail, all the safe violations are declared as unsafe and their
classification as safe has to be verified again.

The new simplex creation is performed using the standard AFT. The
position of the ideal point forming the ideal simplex is
calculated. Then the neighbourhood of the ideal point is searched
to identify already existing points in its vicinity. The best
from the candidates in the neighbourhood or the ideal point, if there
are no candidates, is taken to form a tentative simplex. If the
tentative simplex does not mutually intersect with any already
existing simplex or constraining facet, the point is accepted and
the new simplex is constructed. Otherwise another point is searched for
and the procedure is repeated.

** Next:** Domain Discretization
**Up:** Elimination of Cyclic Violation Dependency
** Previous:** Safe Violation
*Daniel Rypl *

2005-11-06