Project
EF2-4
Conforming Regular Triangulations
Project Heads
Marc Alexa, Hang Si, Boris Springborn
Project Members
–
Project Duration
01.01.2019 – 31.12.2021
Located at
TU Berlin
Description
Delaunay triangulations are fundamental for processing geometry, yet they are too rigid to conform to given shapes. We introduce conforming regular triangulations, offering new ways to generate shapes spaces and discrete Laplace-Beltrami operators. The project investigates their computational and mathematical properties.
Mission
Regular (or weighted Delaunay) triangulations are useful structures for computations (such as FE bases, or shape analysis) because they admit orthogonal dual tessellations – similar to (unweighted) Delaunay triangulations. Yet, they cover a richer combinatorial space compared to Delaunay triangulations and may conform to a variety of boundary configurations without the need for additional (so-called Steiner) vertices.
Research focuses on the necessary mathematical foundation of regular triangulations of point sets as well as developing efficient algorithms for all aspects of computing conforming weighted Delaunay triangulations.
Directions
- An important property of Delaunay triangulations in the plane is that they minimize Dirichlet energy of any PL function (among all possible triangulations of the convex hull of the vertices). Extending this idea to higher dimensions defines harmonic triangulations. It turns out that, unlike in 2D, there is no global combinatorial minimizer of Dirichlet energy. But, similar to 2D, a flip eitehr increases or decreases Dirichlet energy, regardless of the PL function. Harmonic flipping, i.e. flipping towards smaller Dirichlet energy, appears to be an effective tool to improve dihedral angles of a tetrahedral mesh.
- Conforming regular triangulations for triangle meshes can be computed by solving a linear feasibility problem.
In the plane, all simple polygons have triangulations, all these triangulations are connected by flips, and all triangulations of convex polygons are regular. There are no similar results in 3D – quite the opposite: non-convex polyhedra may have no triangulation tetrahedra (and it is NP hard to decide if they have), and it is unknown if triangulations of even convex polyhedra are connected by flips. We have conjectured a class of non-convex polyhedra, we term “skew prismatoids”, to contain only regular triangulations. This means a triangulation, if it exists, can be computed in polynomial time.- Flips are local operations to transform one triangulation into another triangulation of a point set. It is very useful in many triangulation algorithms. However, the global behavior of a sequence of flips is still not well understood in dimensions higher than 3. We studied the geometric and combinatorial properties of a classical algorithm — Lawson’s flip algorithm for constructing Delaunay triangulations in 2d.
A consequence of the above study is a polynomial algorithm to triangulate a class of 3d non-convex polyhedra.
Selected Publications
- Marc Alexa. Harmonic triangulations ACM Transactions on Graphics (TOG), 38, 4, Article 54, July 2019, DOI: 10.1145/3306346.3322986
- Hang Si, On monotone sequences of directed flips, triangulations of polyhedra, and structural properties of a directed flip graph, WIAS Preprint No. 2554, (2018)
- Hang Si, A Simple Algorithm to Triangulate a Special Class of 3d Non-convex Polyhedra Without Steiner Points, In Proceedings of the 9th International Conference, NUMGRID 2018 / Voronoi 150, Celebrating the 150th Anniversary of G.F. Voronoi, Moscow, Russia, December 2018
Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.