5
$\begingroup$

Hoping I'm not misunderstanding the concept here, but it is my understanding that Voronoi Diagrams and Delaunay Tesselations are 'dual' to one another, owing to the fact that each' solution makes computational of the other's solution trivial.

What I'm looking to understand is, why? I mean, it obviously happens, but is there some kind of mathematical proof or principle that justifies that convenient coincidence? Or is it just that, a coincidence?

I suppose, the voronoi quality of 'each vertex is equidistant from the 3 closest points' means that any matching triangulation is a delaunay triangulation (there is no point closer than the closest points), but I am hoping for something more... in-depth? Is there such a thing?

To clarify: the question is not about what them being dual means, like the suggested duplicate. The question is why they behave as duals.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Possible duplicate of How are the Voronoi Tesselation and Delaunay triangulation problems duals of each other? $\endgroup$
    – GoHokies
    May 7, 2019 at 12:57
  • $\begingroup$ Check the last answer in the link provided by GoHokies: en.wikipedia.org/wiki/Dual_graph?wprov=sfla1 $\endgroup$
    – nicoguaro ♦
    May 7, 2019 at 13:19
  • $\begingroup$ @GoHokies that question has a key difference to mine: that one is about how duality is applied for the two graphs. Mine is about how it emerges, or 'why' it is applied. $\endgroup$
    – Thanos Maravel
    May 7, 2019 at 15:41
  • $\begingroup$ @nicoguaro that answer explains how to use the duality to go from one solution to the other. I am hoping for a mechanism to explain why this works in the first place. I'll look into that link when I can focus properly, though, it might help. Not sure why I missed it. $\endgroup$
    – Thanos Maravel
    May 7, 2019 at 15:44

1 Answer 1

Reset to default
5
$\begingroup$

The duality between Voronoi cells and vertices of the triangulation is pretty clear: each vertex of the Delaunay triangulation is a site in the Voronoi diagram which gets associated with its Voronoi cell.

To understand the duality between Delaunay triangles and Voronoi vertices, start by looking at this image from https://stackoverflow.com/questions/42047077/voronoi-site-points-from-delaunay-triangulation:

enter image description here

The Delaunay triangulation is defined by the empty circumcircle property, i.e., three vertices from a Delaunay triangle if and only if the circle passes through them does not contain any other vertices of the triangulation.

In the image, the green circle which is the circumcircle of a Delaunay triangle (since it does not contain any other vertices). The center of that circle is a point that is equidistant from the three vertices on the circle.

But consider this configuration in terms of the Voronoi diagram: a point equidistant from three Voronoi sites is a corner in the Vornoi diagram where three Voronoi cells meet. So each vertex in the Voronoi diagram is the circumcenter of a Delaunay triangle.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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