quick links

Some slide shows.

My publications.

Back home.


Research

My research is in methods for generating Quality Delaunay Meshes of Linear Complices. Roughly speaking, some user gives the computer a bunch of points and segments, and the computer spits back a bunch of triangles, such that each input segment is the union of triangle edges, each input point is a triangle vertex, the triangles are Delaunay with respect to the set of points, and all the triangles are good quality (that is, have no small or large angles).

The original algorithm was found by Jim Ruppert in the early 90's. However, this algorithm had severe restrictions on the input. Namely, input segments had to meet at obtuse angles. This was fixed by Jonathan Shewchuk, with a variant algorithm. However, this fix is more complicated than the original algorithm and wholly lacks a grading guarantee; that is, the output could be a lot of triangles of roughly the same size. Ruppert's algorithm came with a proof that small output triangles would only be near where the input features were close together. Another annoyance is that although Shewchuk's Terminator algorithm can handle input with arbitrarily small angles, the output may contain triangles with far smaller angles, or with very large angles.

Working with Gary Miller and Noel Walkington, I fixed Ruppert's orginal algorithm by changing one of the rules slightly. The fix has the good grading guarantee of Ruppert's original, while having output angle guarantees superior to those of Shewchuk. In fact the upper bound on output angle is independent of the minimum input angle. I also altered Scott Mitchell's cardinality bounds for bounded angle triangulations to get better optimality bounds on output mesh size by exploiting mesh anisotropy.

I also managed to implement this algorithm in sml, with a lot of help from the pscico group at Carnegie Mellon. This includes a whole lot of effort from Umut Acar, Guy Blelloch, and Aleksandar Nanevski, and countless others. The algorithm isn't exactly production code, but it can make pretty pictures.

By the way, working with Gary and Noel is a lot of fun. But you might feel a little left out if you don't own your own airplane! That's ok, because they both ride bicycles to work, which is pretty good in my book.