Similarity measures for (geometric) triangulations

In a project I am working on, we are looking at multiple different (optimal with respect to some cost measure) triangulations of a fixed pointset $$S$$. I would like to cluster similar triangulations.

My first Idea was something like the edge flip distance, i.e. the minimal number of edge-flips in a quadrilateral needed to get from one triangulation to the other. Calculating this number is Np-Hard and since my datasets are not small, there are no algorithms that can calculate the flip distance in reasonable time.

Next I had a look at similarity measures for geometric graphs, but they emphasize the translation and insertion/deletion of points to get from one graph to the other one. These kinds of modifications are not interesting in my case, since the positions of the vertices are fixed for both triangulations.

In the figure two different triangulations on the same pointset are given. Note that we already have a one to one correspondence between the vertices of the two Triangulations, since they are generated with respect to the same set of points.

All in all I would like to know if there are any known similarity measures in the context of graphs/geometric graphs/triangulations, that may be interesting and could possibly be adapted to triangulations.

• Why not simply take the similarity measure as the number of triangles that appear in both triangualtions? In the given example, it is $2$. Commented Sep 24, 2021 at 9:17
• this would be a possibilities! another option would be superimposing the two triangulations and then counting edge intersections (which is an upperbound for the flip distance i think), but I was hoping there would also be more "sophisticated" approaches rooted in graph theory Commented Sep 24, 2021 at 9:49
• The criteria depend largely on what you exactly want to achieve. You have not specified that in your question; otherwise there can be many different possibilities, like maximum or minimum angles of the triangles, sum of perimeters of the triangles, etc. Commented Sep 24, 2021 at 9:54

Of course, you're not so much interested in the similarity of a triangulation $$T$$ to the Delaunay triangulation $$\mathcal{D}$$, but rather between $$T$$ and $$T'$$. Fortunately, there are many ways in which you could use their results.