This blog has been dead for nearly two years. Wow. Graduation, grad school, new countries, new people. Although quite a lot of things have changed since the last time I touched this blog, my passion to learn, try out new things and share my experiences remains unchanged. At least, I still believe so.
What I'm about to write about today is regarding a review that I carried out on a handful of Delaunay triangulation algorithms. If you have heard that term before, you probably must know something about computational geometry, meshing or graphics in general. Good for you. If not, no big deal, just keep on reading.
Barring all the mathematical definitions, a triangulation of a set of points is basically a method of connecting all of the points by forming triangles. For a set of points on a 2D plane, this is very similar to the "connect-the-dots" exercise that you did in primary school. For a set of points in higher dimensional space, one would need tetrahedrons and other higher dimensional simplices to connect the points.
 |
| A triangulation of a set of 2D points |
A Delaunay triangulation is a special type of triangulation, which ensures that the circumcircle of any triangle in the Delaunay triangulation does not contain any points inside it. In other words, if you select any triangle in the triangulation and draw a circle which passes through the 3 vertices of that triangle, then there will be no other points inside that circle. Named after Boris Delaunay, this method generally tends to avoid skinny triangles, and the resulting triangulations have some useful mathematical properties. The way I see it, they just become more aesthetically pleasing.
What I'm going to share with you today is an analysis that I carried out on a few different algorithms for producing these Delaunay triangulations, given a set of 2D points. This work was done as a part of my final project of the 18.335 - Introduction to Numerical Methods class I took at MIT in Fall 2013. In particular, I implemented the "Incremental" and "Divide-and-Conquer" algorithms for Delaunay triangulation in MATLAB, and then compared the expected and worst-case computational costs observed with theoretical estimates found in the literature.
The complete report is available HERE.
I hope at least one of you will find it useful. :)
