Kinetic and Dynamic Delaunay tetrahedralizations in three dimensions

Abstract

We describe the implementation of algorithms to construct and maintain three-dimensional dynamic Delaunay triangulations with kinetic vertices using a three-simplex data structure. The code is capable of constructing the geometric dual, the Voronoi or Dirichlet tessellation. Initially, a given list of points is triangulated. Time evolution of the triangulation is not only governed by kinetic 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. 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.

29 pg (preprint), 12 figures, 1 table Title changed (mainly nomenclature), referee suggestions included, typos corrected, bibliography updated

References in corpus (2)

• Performance of Random Lattice Algorithms
• Dynamical geometry for multiscale dissipative particle dynamics

Cited by in corpus (8)

• Multicellular Tumor Spheroid in an off-lattice Voronoi/Delaunay cell model
• The Cosmic Web: Geometric Analysis
• A modelling approach towards Epidermal homoeostasis control
• Correlating Cell Behavior with Tissue Topology in Embryonic Epithelia
• Modeling emergent tissue organization involving high-speed migrating cells in a flow equilibrium
• Jamming and force distribution in growing epithelial tissue
• Generalized Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics
• Mechanisms of organogenesis of primary lymphoid follicles