# Is the marching triangles algorithm guaranteed to terminate?

Is the marching triangles algorithm guaranteed to terminate (sucessfully)?

The algorithm does roughly speaking:

• iterate over all boundary edges
• project a new point, add a new triangle from the edge and the point, if it's admissible (the new point does not intersect the circumsphere of any existing triangle)
• if it's not admissible, try do connect the edge with the next or previous point (closing non-convex parts of the boundary), if they are admissible
• if it's still not admissible, try to connect a point from the intersected triangle with the edge
• else skip the edge in this iteration

Now i get the following case The algorithm correctly generated a mesh with triangles, by projecting the new points. Now there is a triangular crack, which is not local delaunay.

• projecting a point by a constant distance clearly fails
• using the next, previous or intersection point doesn't generate a admissible triangle
• ignoring the edge leads to a non-closed mesh
• adding the edge for the next iteration leads to a non-terminating algorithm, as it cannot be processed in the next iteration either and no other processed edge will close the hole

The example is a simple implicit circle function as used in the paper, the seed triangle is an arbitrary edge on the implicit function connected with a point projected by the fixed distance and then projected back on the surface as defined in the algorithm.

When i give the next / previous points preference (choose the next / previous point if it is nearer than $\epsilon$, even when a new triangle could be created), i can reduce the number of tight cracks, but it doesn't cover all problem cases either.

Despite the obvious problem with my implementation, i do not see if the algorithm as described in the paper is guaranteed to always find a admissible triangle in an iteration until the edge list is empty.