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

Abstract

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

How to cite

top

Memari, 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
  1. Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, Mathieu Desbrun, Variational Tetrahedral Meshing, ACM Trans. on Graphics (SIGGRAPH) 24 (2005), 617-625 
  2. F. Aurenhammer, A criterion for the affine equivalence of cell complexes in ℝ d and convex polyhedra in ℝ d + 1 , Discrete and Computational Geometry 2 (1987), 49-64 Zbl0608.52006MR879360
  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), 245-261 Zbl0557.76097
  4. Alain Bossavit, Computational Electromagnetism, (1998), Academic Press, Boston Zbl0945.78001MR1488417
  5. Fernando De Goes, Pierre Alliez, Houman Owhadi, Mathieu Desbrun, On the equilibrium of simplicial masonry structures, ACM Transactions on Graphics 32 (2013) Zbl1305.68297
  6. Mathieu Desbrun, Eva Kanso, Yiying Tong, Discrete Differential Forms for Computational Modeling, Discrete Differential Geometry (2007), BobenkoA.A. Zbl1152.58001MR2405673
  7. Qiang Du, Vance Faber, Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Rev. 41 (1999), 637-676 Zbl0983.65021MR1722997
  8. H. Edelsbrunner, Algorithms in Combinatorial Geometry, (1987), Springer-Verlag Zbl0634.52001MR904271
  9. G. Ewald, Combinatorial convexity and algebraic geometry, (1996), Springer Verlag Zbl0869.52001MR1418400
  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, ACM SIGGRAPH Courses (2006), 69-74 MR2354196
  11. I.M. Gelfand, M.M. Kapranov, A.V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, (1994), Springer Zbl0827.14036MR1264417
  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, (2010), Springer Zbl1195.68074MR2676662
  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), 253-294 Zbl1194.74406MR2355176
  15. A. N. Hirani, Discrete Exterior Calculus, (2003) MR2704508
  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), 443-456 Zbl0746.52015MR1116369
  17. Bruno Lévy, Yang Liu, L p Centroidal Voronoi Tesselation and its Applications, ACM Trans. on Graph. 29 (2010) 
  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) 
  19. S. F. McCormick, Multilevel Adaptive Methods for Partial Differential Equations, (1989), SIAM Zbl0707.65080MR1056696
  20. 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
  21. Patrick Mullen, Pooran Memari, Fernando de Goes, Mathieu Desbrun, HOT: Hodge-optimized triangulations, ACM Transactions on Graphics (TOG) 30 (2011) Zbl1322.68217
  22. O.R. Musin, Properties of the Delaunay triangulation, Symposium on Computational Geometry (1997) 
  23. J. Nocedal, S. J. Wright, Numerical optimization, (1999), Springer Verlag Zbl1104.65059MR1713114
  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), 186-208 
  25. F. P. Preparata, M. I. Shamos, Computational Geometry: An Introduction, (1985), Springer-Verlag Zbl0759.68037MR805539
  26. VT Rajan, Optimality of the Delaunay triangulation in ℝ d , Discrete and Computational Geometry 12 (1994), 189-202 Zbl0808.52012MR1283887
  27. E. Steinitz, Polyeder und raumeinteilungen, Encyclopädie der mathematischen Wissenschaften 3 (1922), 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), 75:1-75:9 
  29. G.M. Ziegler, Lectures on polytopes, (1995), Springer Zbl0823.52002MR1311028

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.