I am looking for a "good" way to triangulate a closed concave shape of vertices and edges. "good" is quite a vague term, but the basic principles I'm interested in are: 1) Minimize "sliver" triangles that are very thin and contain really small angles. 2) Must be reasonable to compute. Ideally it would take less than a day to compute the triangulization for a mesh with ~10,000 vertices on a standard computer (so complete brute force is out). Here is a diagram (initial shape in black): http://img394.imageshack.us/img394/3077/concavetriangle.png [Broken] If the mesh was convex, a good strategy would be http://en.wikipedia.org/wiki/Delaunay_trianglulation [Broken] method could work well if I had a fast way of finding the worst possible triangle among a subset of the shape, but I'm having no luck there.