[jgtrosh]

Iirc, triangulation iterations can replace previous cuts. So A and B might not have any meaning in the next iteration if you triangulate properly. That's why it's okay to cut at random, because it only affects outcome indirectly.

[amelius]

Wait a second, are we both talking about Delaunay triangulation?

[jgtrosh]

Yes. After checking Wikipedia I was referring to the edge flipping operation which is described in the “flip algorithms” section. So there's also a divide and conquer algorithm in the article, but it needs extra steps to fix the divide edge. Was that what you were talking about?

[amelius]

Yes, that's what I was thinking about.