[amelius]

Let's say you have a domain X that you need to triangulate. You break it along a plane, into two domains A and B, about equally large.

Imagine that you have a magical black box system that can triangulate A and B.

Would this not help you to triangulate X? I can hardly believe it wouldn't. (Again, perhaps in pathological cases yes, or if a near-optimal solution is not good enough).

[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.