Geometric Aspects of the Space of Triangulations

Memari, Pooran

Actes des rencontres du CIRM, Tome 3 (2013) no. 1, pp. 141-150.

These are the notes of my talk presented in the colloquium on discrete curvature at the CIRM, in Luminy (France) on November 21st, 2013, in which we study the space of triangulations from a purely geometric point of view and revisit the results presented in [21] and [20] (joint works with Patrick Mullen, Fernando De Goes and Mathieu Desbrun). Motivated by practical numerical issues in a number of modeling and simulation problems, we first introduce the notion of a compatible dual complex (made out of convex cells) to a primal triangulation, such that a simplicial mesh and its compatible dual complex form what we call a primal-dual triangulation. Using algebraic and computational geometry results, we show that for simply connected domains, compatible dual complexes exist only for a particular type of triangulation known as weakly regular. We also demonstrate that the entire space of primal-dual triangulations, which extends the well known (weighted) Delaunay/Voronoi duality, has a convenient, geometric parameterization. We finally discuss how this parameterization may play an important role in discrete optimization problems such as optimal mesh generation, as it allows us to easily explore the space of primal-dual structures along with some important subspaces.

[1] Alliez, Pierre; Cohen-Steiner, David; Yvinec, Mariette; Desbrun, Mathieu Variational Tetrahedral Meshing, ACM Trans. on Graphics (SIGGRAPH), Volume 24 (2005) no. 3, pp. 617-625 | DOI

[2] Aurenhammer, F. A criterion for the affine equivalence of cell complexes in ${ℝ}^d$ and convex polyhedra in ${ℝ}^{d+1}$, Discrete and Computational Geometry, Volume 2 (1987) no. 1, pp. 49-64 | DOI | MR | Zbl

[3] Baligaa, B. R.; Patankarb, S. V. A Control Volume Finite-Element Method For Two-Dimensional Fluid Flow And Heat Transfer, Numerical Heat Transfer, Volume 6 (1983), pp. 245-261

[4] Bossavit, Alain Computational Electromagnetism, Academic Press, Boston, 1998 | MR | Zbl

[5] De Goes, Fernando; Alliez, Pierre; Owhadi, Houman; Desbrun, Mathieu On the equilibrium of simplicial masonry structures, ACM Transactions on Graphics, Volume 32 (2013) no. 4 | Zbl

[6] Desbrun, Mathieu; Kanso, Eva; Tong, Yiying Discrete Differential Forms for Computational Modeling, Discrete Differential Geometry (Bobenko, A.; Schröder, P., eds.), Springer, 2007 | Zbl

[7] Du, Qiang; Faber, Vance; Gunzburger, Max Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Rev., Volume 41 (1999), pp. 637-676 | MR | Zbl

[8] Edelsbrunner, H. Algorithms in Combinatorial Geometry, Springer-Verlag, 1987 | DOI | Zbl

[9] Ewald, G. Combinatorial convexity and algebraic geometry, Springer Verlag, 1996 | Zbl

[10] Fisher, Matthew; Springborn, Boris; Bobenko, Alexander I.; Schröder, Peter An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing, ACM SIGGRAPH Courses (2006), pp. 69-74 | Zbl

[11] Gelfand, I.M.; Kapranov, M.M.; Zelevinsky, A.V. Discriminants, resultants, and multidimensional determinants, Springer, 1994 | DOI | Zbl

[12] Glickenstein, D. Geometric triangulations and discrete Laplacians on manifolds, Arxiv preprint math/0508188 (2005)

[13] Grady, Leo J.; Polimeni, Jonathan R. Discrete Calculus: Applied Analysis on Graphs for Computational Science, Springer, 2010 | Zbl

[14] Hauret, P.; Kuhl, E.; Ortiz, M. Diamond Elements: a finite element/discrete-mechanics approximation scheme with guaranteed optimal convergence in incompressible elasticity, Int. J. Numer. Meth. Engng., Volume 72 (2007) no. 3, pp. 253-294 | DOI | MR | Zbl

[15] Hirani, A. N. Discrete Exterior Calculus, Caltech, May (2003) (Ph. D. Thesis) | MR

[16] Lee, C.W. Regular triangulations of convex polytopes, Applied Geometry and Discrete Mathematics–The Victor Klee Festschrift (P. Gritzmann, B. Sturmfels, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc, Volume 4 (1991), pp. 443-456 | MR

[17] Lévy, Bruno; Liu, Yang $L_p$ Centroidal Voronoi Tesselation and its Applications, ACM Trans. on Graph., Volume 29 (2010) no. 4

[18] Liu, Yang; Wang, Wenping; Lévy, Bruno; Sun, Feng; Yan, DongMing; Lu, Lin; Yang, Chenglei On Centroidal Voronoi Tessellation - Energy Smoothness and Fast Computation, ACM Trans. on Graph., Volume 28 (2009) no. 4

[19] McCormick, S. F. Multilevel Adaptive Methods for Partial Differential Equations, SIAM, 1989 | DOI | Zbl

[20] Memari, Pooran; Mullen, Patrick; Desbrun, Mathieu Parametrization of Generalized Primal-Dual Triangulations, Proceedings of the 20th International Meshing Roundtable, Springer, 2012, pp. 237-253

[21] Mullen, Patrick; Memari, Pooran; de Goes, Fernando; Desbrun, Mathieu HOT: Hodge-optimized triangulations, ACM Transactions on Graphics (TOG), Volume 30 (2011) no. 4, 103 pages

[22] Musin, O.R. Properties of the Delaunay triangulation, Symposium on Computational Geometry (1997), 426 pages

[23] Nocedal, J.; Wright, S. J. Numerical optimization, Springer Verlag, 1999 | DOI | Zbl

[24] Paluszny, A.; Matthäi, S.; Hohmeyer, M. Hybrid finite element finite volume discretization of complex geologic structures and a new simulation workflow demonstrated on fractured rocks, Geofluids, Volume 7 (2007), pp. 186-208 | DOI

[25] Preparata, F. P.; Shamos, M. I. Computational Geometry: An Introduction, Springer-Verlag, 1985 | Zbl

[26] Rajan, VT Optimality of the Delaunay triangulation in ${ℝ}^d$, Discrete and Computational Geometry, Volume 12 (1994) no. 1, pp. 189-202 | DOI | MR | Zbl

[27] Steinitz, E. Polyeder und raumeinteilungen, Encyclopädie der mathematischen Wissenschaften, Volume 3 (1922) no. 9, pp. 1-139

[28] Tournois, Jane; Wormser, Camille; Alliez, Pierre; Desbrun, Mathieu Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation, ACM Trans. Graph., Volume 28 (2009), p. 75:1-75:9

[29] Ziegler, G.M. Lectures on polytopes, Springer, 1995