×

Kinetic and dynamic Delaunay tetrahedralizations in three dimensions. (English) Zbl 1196.65039

Summary: We describe algorithms to implement fully dynamic and kinetic three-dimensional unconstrained Delaunay 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.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs

Software:

Voronoi
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] von Neumann, J., Theory of Self-Reproducing Automata (1966), University of Illinois Press
[2] Baer, R.; Martinez, H., Automata and biology, Ann. Rev. Biophys. Bioeng., 3, 255-291 (1974)
[3] Meyer-Hermann, M., A mathematical model for the germinal center morphology and affinity maturation, J. Theoret. Biol., 216, 273-300 (2002)
[4] Meineke, F.; Potten, C.; Loeffler, M., Cell migration and organization in the intestinal crypt using a lattice-free model, Cell Proliferation, 34, 253-266 (2001)
[5] Weliky, M.; Oster, G., The mechanical basis of cell rearrangement, Development, 109, 373-386 (1990)
[6] Weliky, M.; Oster, G.; Minsuk, S.; Keller, R., Notochord morphogenesis in xenopus laevis: simulation of cell behavior underlying tissue convergence and extension, Development, 113, 1231-1244 (1991)
[7] Honda, H., Description of cellular patterns by Dirichlet domains: the two-dimensional case, J. Theoret. Biol., 72, 3, 523-543 (1978)
[8] Honda, H.; Tanemura, M.; Yoshida, A., Differentiation of wing epidermal scale cells in a butterfly under the lateral inhibition model—appearance of large cells in a polygonal pattern, Acta Biotheoret., 48, 121-136 (2000)
[9] Honda, H.; Tanemura, M.; Nagai, T., A three-dimensional vertex dynamics cell model of space-filling polyhedra simulating cell behavior in a cell aggregate, J. Theoret. Biol., 226, 439-453 (2004) · Zbl 1439.92074
[10] J.-A. Ferrez, Dynamic triangulations for efficient 3d simulations of granular materials, Ph.D. thesis, EPFL, thesis 2432, 2001; J.-A. Ferrez, Dynamic triangulations for efficient 3d simulations of granular materials, Ph.D. thesis, EPFL, thesis 2432, 2001 · Zbl 0987.68693
[11] Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S. N., Spatial tessellations: Concepts and applications of Voronoi diagrams, Probability and Statistics (2000), Wiley: Wiley NYC, pp. 671 · Zbl 0946.68144
[12] Berg, M. D.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational Geometry (1997), Springer: Springer Berlin
[13] S. Fortune, Voronoi diagrams and Delaunay triangulations, Computing in Euclidean Geometry 1; S. Fortune, Voronoi diagrams and Delaunay triangulations, Computing in Euclidean Geometry 1 · Zbl 0907.68190
[14] Lürig, C.; Ertl, T., Adaptive iso-surface generation, (3D Image Analysis and Synthesis’96 (1996)), 183-190
[15] Miller, G. L.; Talmor, D.; Teng, S.-H.; Walkington, N., A Delaunay based numerical method for three dimensions: generation, formulation, and partition, (Proceedings of the 27th Annual ACM Symposium on Theory of Computing (1995)), 683-692 · Zbl 0978.68575
[16] Bottino, D. C., Computer simulations of mechanochemical coupling in a deforming domain: applications to cell motion, (IMA Volumes in Mathematics and its Applications, Frontiers in Applied Mathematics Series, vol. 121 (2000)), 295-314 · Zbl 1028.92005
[17] Schönhardt, E., Über die Zerlegung von Dreieckspolyedern in Tetraeder, Math. Annal., 98, 309-312 (1928) · JFM 53.0576.01
[18] Goodman, J.; O’Rourke, J., Handbook of Discrete and Computational Geometry (1997), CRC Press: CRC Press New York · Zbl 0890.52001
[19] G. Brouns, A.D. Wulf, D. Constales, Multibeam data processing: Adding and deleting vertices in a Delaunay triangulation, The Hydrographic Journal 101; G. Brouns, A.D. Wulf, D. Constales, Multibeam data processing: Adding and deleting vertices in a Delaunay triangulation, The Hydrographic Journal 101
[20] Devillers, O., On deletion in Delaunay triangulation, Internat. J. Comput. Geom. Appl., 12, 193-205 (2002) · Zbl 1152.68663
[21] Shewchuk, J. R., Constrained Delaunay tetrahedralizations and provably good boundary recovery, (Eleventh International Meshing Roundtable, Sandia National Laboratories (2002)), 193-204
[22] Shewchuk, J. R., A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations, (Proc. 14th Annual Symposium on Computational Geometry (1998)), 76-85
[23] Edelsbrunner, H.; Shah, N., Incremental topological flipping works for regular triangulations, Algorithmica, 15, 223-241 (1996) · Zbl 0840.68050
[24] Mücke, E., A robust implementation for three-dimensional Delaunay triangulations, Internat. J. Comput. Geom. Appl., 2, 8, 255-276 (1998) · Zbl 1035.68539
[25] Xinjian, X.; Franco, R.; Hubert, T.; Liebling, T.; Mocellin, A., The Laguerre model for grain growth in three dimensions, Philosophical Magazine B, 75, 4, 567-585 (1997)
[26] J. Sauer, Allgemeine Kollisionserkennung und Formrekonstruktion basierend auf Zellkomplexen, Ph.D. thesis, Universität des Saarlandes, Fachbereich 14 Informatik, 1995; J. Sauer, Allgemeine Kollisionserkennung und Formrekonstruktion basierend auf Zellkomplexen, Ph.D. thesis, Universität des Saarlandes, Fachbereich 14 Informatik, 1995
[27] Aurenhammer, F.; Imai, H., Geometric relations among Voronoi diagrams, Geom. Dedicata, 27, 65-75 (1988) · Zbl 0642.52008
[28] Shewchuk, J. R., Adaptive precision floating-point arithmetic and fast robust geometric predicates, (Arithmetic, A. P.F.-P.; Predicates, F. R.G., Discrete and Computational Geometry, vol. 18 (1997)), 305-363 · Zbl 0892.68098
[29] Kittel, C., Introduction to Solid State Physics (1996), John Wiley and Sons
[30] Aurenhammer, F., Voronoi diagrams—a survey of fundamental geometric data structure, ACM Comput. Surv., 23, 3, 345-405 (1991)
[31] Boissonnat, J.-D.; Teillaud, M., On the randomized construction of the Delaunay tree, Theoret. Comput. Sci., 112, 2, 339-354 (1993) · Zbl 0780.68110
[32] Choi, T. J., Generating optimal computational grids: Overview and review, 1997
[33] Devillers, O.; Pion, S.; Teillaud, M., Walking in a triangulation, (Proc. 17th Annu. Sympos. Comput. Geom. (2001)), 106-114 · Zbl 1374.68659
[34] M.A. Facello, Constructing Delaunay and regular triangulations in three dimensions, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1993; M.A. Facello, Constructing Delaunay and regular triangulations in three dimensions, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1993
[35] Bowyer, A., Computing Dirichlet tessellations, Comput. J., 24, 2, 162-166 (1981)
[36] Devillers, O., Improved incremental randomized Delaunay triangulation, (Proc. 14th Annu. ACM Sympos. Comput. Geom. (1998)), 106-115
[37] Mücke, E. P.; Saias, I.; Zhu, B., Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations, (Proc. 12th Annu. ACM Sympos. Comput. Geom. (1996)), 274-283
[38] Devroye, L.; Mücke, E. P.; Zhu, B., A note on point location in Delaunay triangulations of random points, Algorithmica, 22, 477-482 (1998) · Zbl 0914.68201
[39] De Fabritiis, G.; Coveney, P. V., Dynamical geometry for multiscale dissipative particle dynamics, Comp. Phys. Commun., 153, 209-226 (2003) · Zbl 1196.76063
[40] Lauritsen, K. B.; Puhl, H.; Tillemans, H.-J., Performance of random lattice algorithms, Internat. J. Modern Phys. C, 5, 6, 909-922 (1994)
[41] Mostafavi, M. A.; Gold, C.; Dakowicz, M., Delete and insert operations in Voronoi/Delaunay methods and applications, Comput. Geosci., 29, 523-530 (2003)
[42] Boissonnat, J.-D.; Yvinec, M., Algorithmic Geometry (1998), Cambridge University Press: Cambridge University Press Cambridge
[43] M. Vigo, N. Pla, Regular triangulations of dynamic sets of points, 2000; M. Vigo, N. Pla, Regular triangulations of dynamic sets of points, 2000 · Zbl 0995.68151
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.