Search code examples
uniquetriangulationdelaunay

In Delaunay triangulation D(P), If one point is added in point set P, then all the triangulation is broken?

In Wikipedia, the definition of Delaunay triangulation,

"a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P)"

Here, moreover, wiki says, "Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation"

When one point is added inside one of the triangles, then every triangle changes differently or just the triangle which contains the added point breaks into several triangles?

If you know research paper or website about this topic, please let me know~ :)

Solution

  • It will affect more than just triangle containing the point, but it won't affect entire graph. 'Intuition' is that it rearrange triangle distribution towards all nearest points.

    Playing around with this http://bl.ocks.org/mbostock/4341156 will probably give you better idea of how it behaves.