Kinetic and dynamic Delaunay tetrahedralizations in three dimensions

We describe algorithms to implement fully dynamic and kinetic three-dimensional unconstrained Delatmay triangulations, where the time evolution of the triangulation is not only governed by moving vertices but also by a changing number of vertices. We use three-dimensional simplex flip algorithms, a stochastic visibility walk algorithm for point location and in addition, we propose a new simple method of deleting vertices from an existing three-dimensional Delaunay triangulation while maintaining the Delaunay property. As an example, we analyse the performance in various cases of practical relevance. The dual Dirichlet tessellation can be used to solve differential equations on an irregular grid, to define partitions in cell tissue simulations, for collision detection etc. (C) 2004 Elsevier B.V. All rights reserved.