0
$\begingroup$

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?

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.