Fully Dynamic Constrained Delaunay

Summary. We present algorithms for the efficient insertion and removal of con-straints in Delaunay Triangulations. Constraints are considered to be points or any kind of polygonal lines. Degenerations such as edge overlapping, self-intersections or duplicated points are allowed and are automatically detected and fixed on line. As a result, a fully Dynamic Constrained Delaunay Triangulation is achieved, able to efficiently maintain a consistent triangulated representation of dynamic polygo-nal domains. Several applications in the fields of data visualization, reconstruction, geographic information systems and collision-free path planning are discussed