# Delaunay triangulation: Finding all triangles with empty circumcircle

I have a set of points and I want to find all possible triangles which have empty circumcircle. I want to use Delaunay Triangulation.

I have read some papers on the subject but I am not sure whether Delaunay Triangulation finds all possible triangles or not. If yes, then how can I mathematically prove that?

• No, it does not. – Moishe Kohan Dec 14 '13 at 17:51
• Is there any way to find all possible triangles which have the same properties as Delaunay? – Scorpionidas Dec 14 '13 at 18:36

## 2 Answers

To find all possible triangles you can make all the faces the same length:https://stackoverflow.com/questions/20695680/i-found-an-algorithm-for-computing-multiple-msts-in-oe-v-is-this-publishable.

From your original question on SO:

Here is a proof: Assume that p, q, r are three points of P not on a common line such that no other point of P is in the circle C defined by p, q, r. Then the center of C is a Voronoi node of the Voronoi diagram V(P) of P. Note that V(P) is the dual graph of the Delaunay triangulation D(P) of P: Every Voronoi node belongs to a Delaunay triangle (and vice versa). The dual of the node mentioned above is your triangle.

See "Computational Geometry" by de Berg, Cheong, van Kreveld, Overmars for basic properties on Voronoi diagrams and Delaunay triangulations.