1
$\begingroup$

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.

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ Why not simply take the similarity measure as the number of triangles that appear in both triangualtions? In the given example, it is $2$. $\endgroup$
    – Inuyasha Yagami
    Commented Sep 24, 2021 at 9:17
  • $\begingroup$ 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 $\endgroup$
    – Philip Mayer
    Commented Sep 24, 2021 at 9:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Inuyasha Yagami
    Commented Sep 24, 2021 at 9:54

1 Answer 1

Reset to default
1
$\begingroup$

Near Delaunay

There has been some recent research on this topic. Specifically, the paper Near-Delaunay Metrics by Beusekom et al. investigates the similarity of arbitrary triangulations to a Delaunay triangulation. Some of this has been inspired by the notion that a Delaunay triangulation of a point-set is one of the "nicest" triangulations there are, and so it might be worth our while whether we can measure the distance of a triangulation to a Delaunay triangulation.

Application to general similarity

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.

You could directly apply one of their metrics and cluster purely based on the "nearness to Delaunay". Another option is clustering on in which of their metrics the triangulation is closest to the Delaunay triangulation.

It's probably better to also try to use their ideas and create a method on your own. This will depend on your application, requires prototyping, experimenting, and testing. So, that part will be up to you. Good luck!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.