**Up:** Top
** Previous:** Bibliography

**Figure 1:**
Various triangulations of a 2D set of points: a) general
triangulation, b) constrained triangulation, c) Delaunay
triangulation, d) constrained Delaunay triangulation (constraining
edges are in bold).

**Figure 2:**
Boundary recovery - transformation of 2D Delaunay triangulation into constrained
Delaunay triangulation using the diagonal (of shaded quadrilateral) swapping.

**Figure 3:**
Violation dependency: a) set of points

and constraining
edges

with their smallest circumscribed circles

, b) dependency
graph corresponding to the violation of the empty-circumsphere property of
constraining edges, c) possible point insertion ordering ensuring
presence of all constraining edges in the constrained Delaunay triangulation.

**Figure 4:**
Cyclic violation dependency: a) set of points

and constraining
edges

with their smallest circumscribed circles

, b) dependency
graph corresponding to the violation of the empty-circumsphere property of
constraining edges.

**Figure 5:**
Cyclic violation dependency graph: a) set of points

and constraining
edges

with their smallest circumscribed circles

, b) dependency
graph corresponding to the violation of the empty-circumsphere property of
constraining edges.

**Figure 6:**
Perturbation of point

to remove its violation of constraining
edge

: a) using perpendicular shift, b) using
radial shift to setup its initial position before the iterative
adjustment toward the final position

.

**Figure 7:**
Save violation of

: a) without, b) with additional dependencies.

**Figure 8:**
Save violation of

with

existing in the Delaunay
triangulation: a) side view in the direction of

, b) top view
perpendicularly to

. Shaded area should comply with empty-property.

**Figure 9:**
Simple topological transformation. 2 tetrahedra are made
from 3 by removal of edge

intersecting constraining face

.

**Figure 10:**
Safe violation of

due to simple topological
transformation: a) side view in the direction of

, b) top view
perpendicularly to

. Shaded area should comply with
empty-property. All edges

bounding

have to be successively
considered.

**Up:** Top
** Previous:** Bibliography
*Daniel Rypl *

2005-11-06