Center for diffusion of mathematic journals


Actes des rencontres du CIRM

Table of contents for this issue | Previous article | Next article
Pooran Memari
Geometric Aspects of the Space of Triangulations
Actes des rencontres du CIRM, 3 no. 1: Discrete curvature: Theory and applications (2013), p. 141-150, doi: 10.5802/acirm.63
Article PDF

Résumé - Abstract

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] Pierre Alliez, David Cohen-Steiner, Mariette Yvinec & Mathieu Desbrun, “Variational Tetrahedral Meshing”, ACM Trans. on Graphics (SIGGRAPH) 24 (2005) no. 3, p. 617-625
[2] F. Aurenhammer, “A criterion for the affine equivalence of cell complexes in $\mathbb{R}^d$ and convex polyhedra in $\mathbb{R}^{d+1}$”, Discrete and Computational Geometry 2 (1987) no. 1, p. 49-64  MR 879360 |  Zbl 0608.52006
[3] B. R. Baligaa & S. V. Patankarb, “A Control Volume Finite-Element Method For Two-Dimensional Fluid Flow And Heat Transfer”, Numerical Heat Transfer 6 (1983), p. 245-261  Zbl 0557.76097
[4] Alain Bossavit, Computational Electromagnetism, Academic Press, Boston, 1998  MR 1488417 |  Zbl 0945.78001
[5] Fernando De Goes, Pierre Alliez, Houman Owhadi, Mathieu Desbrun & , “On the equilibrium of simplicial masonry structures”, ACM Transactions on Graphics 32 (2013) no. 4
[6] Mathieu Desbrun, Eva Kanso & Yiying Tong, Discrete Differential Forms for Computational Modeling, in A. Bobenko, P. Schröder, ed., Discrete Differential Geometry, Springer, 2007  MR 2405673 |  Zbl 1152.58001
[7] Qiang Du, Vance Faber & Max Gunzburger, “Centroidal Voronoi Tessellations: Applications and Algorithms”, SIAM Rev. 41 (1999), p. 637-676  MR 1722997 |  Zbl 0983.65021
[8] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987  MR 904271 |  Zbl 0634.52001
[9] G. Ewald, Combinatorial convexity and algebraic geometry, Springer Verlag, 1996  MR 1418400 |  Zbl 0869.52001
[10] Matthew Fisher, Boris Springborn, Alexander I. Bobenko & Peter Schröder, An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing, in ACM SIGGRAPH Courses, 2006, p. 69-74  MR 2354196
[11] I.M. Gelfand, M.M. Kapranov & A.V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Springer, 1994  MR 1264417 |  Zbl 0827.14036
[12] D. Glickenstein, “Geometric triangulations and discrete Laplacians on manifolds”, Arxiv preprint math/0508188 (2005)
[13] Leo J. Grady & Jonathan R. Polimeni, Discrete Calculus: Applied Analysis on Graphs for Computational Science, Springer, 2010  MR 2676662 |  Zbl 1195.68074
[14] P. Hauret, E. Kuhl & M. Ortiz, “Diamond Elements: a finite element/discrete-mechanics approximation scheme with guaranteed optimal convergence in incompressible elasticity”, Int. J. Numer. Meth. Engng. 72 (2007) no. 3, p. 253-294  MR 2355176 |  Zbl 1194.74406
[15] A. N. Hirani, Discrete Exterior Calculus, Ph. D. Thesis, Caltech, 2003  MR 2704508
[16] C.W. Lee, “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 4 (1991), p. 443-456  MR 1116369 |  Zbl 0746.52015
[17] Bruno Lévy & Yang Liu, “$L_p$ Centroidal Voronoi Tesselation and its Applications”, ACM Trans. on Graph. 29 (2010) no. 4
[18] Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, DongMing Yan, Lin Lu & Chenglei Yang, “On Centroidal Voronoi Tessellation - Energy Smoothness and Fast Computation”, ACM Trans. on Graph. 28 (2009) no. 4
[19] S. F. McCormick, Multilevel Adaptive Methods for Partial Differential Equations, SIAM, 1989  MR 1056696 |  Zbl 0707.65080
[20] Pooran Memari, Patrick Mullen & Mathieu Desbrun, Parametrization of Generalized Primal-Dual Triangulations, Proceedings of the 20th International Meshing Roundtable, Springer, 2012, p. 237–253
[21] Patrick Mullen, Pooran Memari, Fernando de Goes & Mathieu Desbrun, “HOT: Hodge-optimized triangulations”, ACM Transactions on Graphics (TOG) 30 (2011) no. 4
[22] O.R. Musin, Properties of the Delaunay triangulation, in Symposium on Computational Geometry, 1997
[23] J. Nocedal & S. J. Wright, Numerical optimization, Springer Verlag, 1999  MR 1713114 |  Zbl 1104.65059
[24] A. Paluszny, S. Matthäi & M. Hohmeyer, “Hybrid finite element finite volume discretization of complex geologic structures and a new simulation workflow demonstrated on fractured rocks”, Geofluids 7 (2007), p. 186-208
[25] F. P. Preparata & M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985  MR 805539 |  Zbl 0759.68037
[26] VT Rajan, “Optimality of the Delaunay triangulation in $\mathbb{R}^d$”, Discrete and Computational Geometry 12 (1994) no. 1, p. 189-202  MR 1283887 |  Zbl 0808.52012
[27] E. Steinitz, “Polyeder und raumeinteilungen”, Encyclopädie der mathematischen Wissenschaften 3 (1922) no. 9, p. 1-139
[28] Jane Tournois, Camille Wormser, Pierre Alliez & Mathieu Desbrun, “Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation”, ACM Trans. Graph. 28 (2009), p. 75:1-75:9
[29] G.M. Ziegler, Lectures on polytopes, Springer, 1995  MR 1311028 |  Zbl 0823.52002
Copyright Cellule MathDoc 2019 | Credit | Site Map