04.25

The meshing problem asks how to partition a region (in two or three dimensions) into a small number of nice looking pieces. This is a fundamental problem in engineering used in almost any physical simulation performed on a computer.

The most basic version of this problem is where you are given a point set in the plane (say inside the unit square), and you would like to add (few) points to the point set and compute the best possible triangulation. Best can differ, but a standard measure is that the minimum angle in the triangulation is maximized. Of course, you would like to have a triangulation with as few triangles as possible.

This problem is relatively easy to state, but it is notoriously hard to make progress on it. And unlike other hard theoretical problems making progress on this problem has impact on the real world applications. The standard solutions includes quadtree refinement (see this nice paper by Bern, Eppstein and Gilbert) – which is useless in practice (constants) but theoretically optimal. Another standard technique which is widely used in practice is Delaunay refinement.