CFCS Invited Talks

Harmonic Triangulations

  • Prof. Marc Alexa, Technische Universität Berlin
  • Time: 2019-08-25 10:00
  • Host: Prof. Baoquan Chen
  • Venue: Room 206, Courtyard No.5, Jingyuan


We introduce the notion of harmonic triangulations: a harmonic triangulation simultaneously minimizes the Dirichlet energy of all piecewise linear functions. By a famous result of Rippa, Delaunay triangulations are the harmonic triangulations of planar point sets. We prove by explicit counterexample that in 3D a harmonic triangulation does not exist in general. However, we show that bistellar flips are harmonic: if they decrease Dirichlet energy for one set of function values, they do so for all. This observation gives rise to the notion of locally harmonic triangulations. We demonstrate that locally harmonic triangulations can be efficiently computed, and efficiently reduce sliver tetrahedra. The notion of harmonic triangulation also gives rise to a scalar measure of the quality of a triangulation, which can be used to prioritize flips and optimize the position of vertices. Tetrahedral meshes generated by optimizing this function generally show better quality than Delaunay-based optimization techniques.


Marc Alexa is a Professor in the Faculty of Electrical Engineering and Computer Science at the Technical University of Berlin and heads the Computer Graphics group. He is interested in creating, processing, and manufacturing shapes, as well as intuitive interfaces for these tasks. He holds a masters and PhD degree in Computer Science from Darmstadt University of Technology. He has been Technical Papers Chair for SIGGRAPH 2013, and has chaired several other committees and boards. He received an ERC Starting Grant, the Heinz Maier-Leibnitz prize, as well as other cross-disciplinary grants and awards. He is currently the editor in chief of ACM Transactions on Graphics.