# Geometric Aspects of the Space of Triangulations

Pooran Memari^{[1]}

- [1] CNRS-LTCI, Télécom-ParisTech

Actes des rencontres du CIRM (2013)

- Volume: 3, Issue: 1, page 141-150
- ISSN: 2105-0597

## Access Full Article

top## Abstract

top## How to cite

topMemari, Pooran. "Geometric Aspects of the Space of Triangulations." Actes des rencontres du CIRM 3.1 (2013): 141-150. <http://eudml.org/doc/275332>.

@article{Memari2013,

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.},

affiliation = {CNRS-LTCI, Télécom-ParisTech},

author = {Memari, Pooran},

journal = {Actes des rencontres du CIRM},

language = {eng},

month = {11},

number = {1},

pages = {141-150},

publisher = {CIRM},

title = {Geometric Aspects of the Space of Triangulations},

url = {http://eudml.org/doc/275332},

volume = {3},

year = {2013},

}

TY - JOUR

AU - Memari, Pooran

TI - Geometric Aspects of the Space of Triangulations

JO - Actes des rencontres du CIRM

DA - 2013/11//

PB - CIRM

VL - 3

IS - 1

SP - 141

EP - 150

AB - 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.

LA - eng

UR - http://eudml.org/doc/275332

ER -

## References

top- Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, Mathieu Desbrun, Variational Tetrahedral Meshing, ACM Trans. on Graphics (SIGGRAPH) 24 (2005), 617-625
- 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), 49-64 Zbl0608.52006MR879360
- 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), 245-261 Zbl0557.76097
- Alain Bossavit, Computational Electromagnetism, (1998), Academic Press, Boston Zbl0945.78001MR1488417
- Fernando De Goes, Pierre Alliez, Houman Owhadi, Mathieu Desbrun, On the equilibrium of simplicial masonry structures, ACM Transactions on Graphics 32 (2013) Zbl1305.68297
- Mathieu Desbrun, Eva Kanso, Yiying Tong, Discrete Differential Forms for Computational Modeling, Discrete Differential Geometry (2007), BobenkoA.A. Zbl1152.58001MR2405673
- Qiang Du, Vance Faber, Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Rev. 41 (1999), 637-676 Zbl0983.65021MR1722997
- H. Edelsbrunner, Algorithms in Combinatorial Geometry, (1987), Springer-Verlag Zbl0634.52001MR904271
- G. Ewald, Combinatorial convexity and algebraic geometry, (1996), Springer Verlag Zbl0869.52001MR1418400
- 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, ACM SIGGRAPH Courses (2006), 69-74 MR2354196
- I.M. Gelfand, M.M. Kapranov, A.V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, (1994), Springer Zbl0827.14036MR1264417
- D. Glickenstein, Geometric triangulations and discrete Laplacians on manifolds, Arxiv preprint math/0508188 (2005)
- Leo J. Grady, Jonathan R. Polimeni, Discrete Calculus: Applied Analysis on Graphs for Computational Science, (2010), Springer Zbl1195.68074MR2676662
- 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), 253-294 Zbl1194.74406MR2355176
- A. N. Hirani, Discrete Exterior Calculus, (2003) MR2704508
- 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), 443-456 Zbl0746.52015MR1116369
- Bruno Lévy, Yang Liu, ${L}_{p}$ Centroidal Voronoi Tesselation and its Applications, ACM Trans. on Graph. 29 (2010)
- 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)
- S. F. McCormick, Multilevel Adaptive Methods for Partial Differential Equations, (1989), SIAM Zbl0707.65080MR1056696
- Pooran Memari, Patrick Mullen, Mathieu Desbrun, Parametrization of Generalized Primal-Dual Triangulations, Proceedings of the 20th International Meshing Roundtable (2012), 237-253, Springer Zbl1322.68217
- Patrick Mullen, Pooran Memari, Fernando de Goes, Mathieu Desbrun, HOT: Hodge-optimized triangulations, ACM Transactions on Graphics (TOG) 30 (2011) Zbl1322.68217
- O.R. Musin, Properties of the Delaunay triangulation, Symposium on Computational Geometry (1997)
- J. Nocedal, S. J. Wright, Numerical optimization, (1999), Springer Verlag Zbl1104.65059MR1713114
- 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), 186-208
- F. P. Preparata, M. I. Shamos, Computational Geometry: An Introduction, (1985), Springer-Verlag Zbl0759.68037MR805539
- VT Rajan, Optimality of the Delaunay triangulation in ${\mathbb{R}}^{d}$, Discrete and Computational Geometry 12 (1994), 189-202 Zbl0808.52012MR1283887
- E. Steinitz, Polyeder und raumeinteilungen, Encyclopädie der mathematischen Wissenschaften 3 (1922), 1-139
- Jane Tournois, Camille Wormser, Pierre Alliez, Mathieu Desbrun, Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation, ACM Trans. Graph. 28 (2009), 75:1-75:9
- G.M. Ziegler, Lectures on polytopes, (1995), Springer Zbl0823.52002MR1311028

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.