I am working on a library that requires subdivision of polygons into triangles. The polygons are divided into triangles by (more or less) random points that are inside them. In general, the approach is to perform the Delaunay triangulation on a set of those points. This works very well, however sometimes I get intersecting triangles in my outcome. This case happens when I have more than three co-circular points. For the Delaunay triangulation I am using simple Watson's algorithm. My questions are:
what to do in case of four or more co-circular points. None of the CG books I've read does not mention about handling it. Just that it is some special case.
Are there other triangulations (similar to Delaunay - I cannot insert any additional points) I could potentially use.