Research Projects

Algorithms for the Triangulation of planar straight line graphs.

A planar straight line graph (PSLG) is a set of planar points and a set (non-intersecting) line segments connecting pairs of the points. A triangulation of a PSLG is a set of non-intersecting line segments that connect all the points into a network of triangles. Triangulations are a natural way to organize two-dimensional data. (They are the two dimensional analogue of sorting.) Triangulations have applications in areas such as geography, pattern analysis, computer graphics, crystallography, surface fitting, and finite element methods.

I am conducting research into the nature of such triangulations (which ones can be efficiently computed?), designing algorithms for their computation (can we find an algorithm for the efficient computation of the generalized Delaunay triangulation of a PSLG?), and measuring performance of triangulation algorithms (which published algorithm is fastest in practice?).

Algorithms for 3d Convex Hulls

This is a natural generalization of planar triangulations. To help understand these algorithms I have created a Java applet that animates them.

Virtual Reality

I've been helping some of my students build VRML models of the UNSW Kensington campus and a chemical plant.
Tim Lambert
Last modified: Thu Aug 19 04:31:38 GMT 1999