Checking if point set triangle subdivision is a triangulation

Question

I've been studying Delaunay triangulation (not a homework) and I thought about the following problem : given a set of points S on plane (with cardinality of n) and a set of triangles T (should be with the cardinality of n-2) — how to determine if the triangles set T form a Delaunay triangulation DT(S)?

The first problem is that Delaunay triangulation is not unique, so rebuilding it for the points set again and comparing to the triangles set won't give us the answer. In addition, optimal Delaunay triangulation algorithms are rather hard to implement (however, using libraries like CGAL would have been okay).

Suppose we know how to check if the triangles set is a triangulation (not necessarily Delaunay). Then we should use the definition of a Delanuay triangulation: for every triangle t in triangulation, no point in S is strictly inside the circumference of t. This leads us to the following methods:

1. The trivial approach. Just iterate over T, compute the circumference and iterate over S, checking if point is inside the circumference. However, this takes O(n^2) time, which is not very optimal.
2. The enchanted approach. Again, iterate over T and compute the circumference. If any point s in inside the circumference, it means that its distance to the circumference center is less than the radius. Using nearest neighbour searching structures over S, we will speed up our algorithm. For instance, simple kd-tree structure leads us to O(n log n) algorithm in average and O(n sqrt(n)) in the worst case.
3. Does anyone have an idea of something simpler?

Now let's return to the problem of checking if T is a triangulation at all. Trivial pre-requirements like equality of S and the set of triangles' vertices can be performed no faster than O(n log n). What is left — to check that every two triangles in T intersect in a common face, or not at all.

1. Again, we could do this by iterating over T and again over T, checking for intersection, but this is O(n^2) algorithm.
2. Let's think about what «triangles t1 and t2 intersect» mean? They intersect if their edges intersect or if one triangle is completely lies in another. The problem of intersecting all the edges can be solved at O(n log n) time using Bentley-Ottmann algorithm (the worst case is O((n + k) log n), where k is the count of intersections, but we can stop the algorithm at the moment we find the first intersection). Also we didn't recognize the case of one triangle completely containing another, but I believe we can modify Bentley-Ottmann algorithm to maintain triangles crossing the sweep line instead of segments, which as I said, yields us O(n log n) algorithm. However, it is really complex to implement.
3. I've thought about iterative algorithm — let's maintain the structure of non-intersecting (or only intersecting by edge) triangles (it should be something very similar to kd-tree). Then we try to add the next triangle t: first check if any of t's vertices is already in one of the triangles — then we got an intersection. Otherwise, add t to the structure. However, if we want O(log n) or O(sqrt(n)) time for search and add queries, we have to balance this structure's height, which is too hard even for kd-trees.

So, does anyone know any simple solution to this problem?

Answer 1

There is a Delaunay lemma : "If every edge in a triangulation K of S is locally Delaunay then K is the Delaunay triangulation of S". Maybe this could help in situation from paragraph 1 of your question, where you are certain that K is some triangulation of S. Dunno the computational complexity of this approach though.