Geometric Aspects of the Space of Triangulations

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.