Delaunay Milestone


Triangulation is an important tool in computational geometry, because it allows us to take a complicated shape and approximate it well by a collection of triangles, whose properties we understand. Instead of shape analysis, we will be looking at problems in which we start with a scattered set of points in the plane. A triangulation constructs the maximal number of non-intersecting triangles based on these points. For a given set of points there are many triangulations possible; the Delaunay triangulation is considered the best triangulation, as it does the best job of avoiding the use of small angles.

Topics we will need to learn include:


Last revised on 29 October 2016.