How to Efficiently Triangulate a Concave Shape?

[maze]

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

If the mesh was convex, a good strategy would be http://en.wikipedia.org/wiki/Delaunay_trianglulation 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.

 

[mathman]

Suggestion (it may not be very good): Form the convex hull of the polygon. Use Delaunay, being careful you don't cross any existing lines. Get rid of lines outside original polygon.

 

[maze]

I think the Delaunay triangulization is unique