Efficient updating of Delaunay triangulations in physical simulations

(Russel, Guibas)

Delaunay triangulations provide at once meshes of objects with well-shaped elements, as well as proximity information useful for collision detection. They are extensively used in our project, for instance within the ProShape software for computing the surface area and volume of proteins. We have been investigating algorithms that allow incremental updating of the Delaunay triangulation as the defining nodes move in small steps under a physical simulation model. A variety of approaches are possible, including kinetic data structures, hierarchical decompositions, and node deletion and re-insertion.