** Next:** About this document ...
** Up:** Incremental DELAUNAY TRIANGULATION and
** Previous:** Mesh Refinement

Edge operations form the basis of the incremental algorithm.
Therefore, it is convenient to describe triangulation with
edge-oriented data structures Guibas and Stolfi (1985). I have followed the idea
of Hansen and Levin (1992) of associating with each edge two pointers to the
end points and two pointers to the adjacent triangles. The triangle
structure is defined by three pointers to the edges of a triangle.
Additionally, as required by the point location algorithm, each
triangle has a pointer to its ``children.'' This pointer is NULL when
the triangle belongs to the current Delaunay triangulation.
Many researchers have pointed out that the geometric
primitives used in triangulation must be robust with respect to
round-off errors of finite-precision calculation. To assure the
robustness of the code, I used the adaptive-precision predicates of
Shewchuk (1996), available as a separate package from the
`netlib` public-domain archive.

** Next:** About this document ...
** Up:** Incremental DELAUNAY TRIANGULATION and
** Previous:** Mesh Refinement
Stanford Exploration Project

10/9/1997