9
$\begingroup$

I have always been told that the Voronoi diagram is the dual of the Delaunay triangulation problem. In what sense can they be duals of each other? I thought that dual problems (i.e. in linear programming) are supposed to produce the same answer. Clearly, the two problems do not have the same solution. How can we consider them duals?

$\endgroup$
  • 1
    $\begingroup$ Duality can have different meanings in different contexts. For instance, function spaces can have dual spaces; the dual space of a function space $V$ is the set of all linear functionals on $V$. See the Wikipedia articles on duality in mathematics and list of duality principles for examples. Given that background, the question "what does it mean to be a dual problem" is both too vague and too broad, because it is context-dependent. $\endgroup$ – Geoff Oxberry Jan 15 '12 at 4:19
  • $\begingroup$ That's true, but in this case, I'm referring specifically to duality in the sense of this particular problem $\endgroup$ – Paul Jan 15 '12 at 20:42
  • $\begingroup$ I figured, so I edited out the part where you asked "What does it mean to be a dual problem?" in a more general setting. $\endgroup$ – Geoff Oxberry Jan 16 '12 at 0:34
11
$\begingroup$

The simple answer is that they are dual because for every delaunay triangulation there exists one and only one corresponding voronoi tessellation and vise versa. Thats true for most cases, but there are cases were the correspondence is not one to one. For example in the case when the voronoi tessellation is a regular square grid.

Both the voronoi tessellation and the delaunay triangulation are non-trivial to calculate for a given set of points. But once you have found one the other one is easy to find.

In the delaunay triangulation of a set of points, $P$, all triangles are "delaunay", meaning that there are no points inside the circumcircle corresponding to any of the triangles.

The voronoi tessellation for a set of points, $P$, consists of the set of voronoi cells $R$, such that for every point in $R_i$ are closer to $P_i$ then to any other point in $P$.

Given the delaunay triangulation simply connect the neighboring triangles circumcircle centers.

Given the set of points $P$ and the voronoi tessellation simply connect neighboring cells points. This is of course given that you know the set of point $P$ used when constructing the voronoi tessellation.

$\endgroup$
11
$\begingroup$

Just to illustrate what others are saying: the blue below is the Voronoi diagram, the red the dual Delaunay triangulation. They are dual to one another as geometric plane graphs. From the Voronoi diagram it is trivial to derive the Delaunay triangulation. The reverse direction is not so obvious, but it remains true that from the Delaunay triangulation and some calculation you can compute the Voronoi diagram.
          Vor Diag Del Tri
I computed these diagrams for 50 random points in Mathematica using the ComputationalGeometry package. See this link for my code.

$\endgroup$
  • $\begingroup$ Thanks for the info. It's too bad that Mathematica only does unweighted Voronoi tessellations; we could have used such a capability a few months back for a project! $\endgroup$ – aeismail Jan 17 '12 at 8:26
  • $\begingroup$ It is pretty easy to do in Python too. Check out scipy.spatial. $\endgroup$ – meawoppl Mar 31 '12 at 0:16
4
$\begingroup$

The two problems ask to come up with tilings that are effectively the reverse of each other: the Voronoi tessellation of a set of points ${\bf P}$ is the set of geometric objects ${\bf G}$ such that every point in the interior of object $G_i$ is closer to point $P_i$ than it is to any other point $P_j \in {\bf P}, j \neq i$. The Delaunay triangulation is effectively the reverse of this: it is the set of triangles that join together the set of points ${\bf P}$.

In a sense, this is similar to the duality existing between triangular and hexagonal lattices in statistical physics. The midpoints of the cells in an equilateral triangular lattice, when connected form a hexagonal lattice, and vice versa.

However, it should be pointed out that not all Voronoi tessellations are duals of Delaunay triangulations; this relationship is probably valid only for unweighted Voronoi tessellations. For weighted tessellation methods, in which something other than the Euclidean distance is used to determine the edges, the corresponence breaks down.

$\endgroup$
3
$\begingroup$

To elaborate on the comment by Geoff: Delaunay triangulation and Voronoi diagrams are "objects" rather than "problems". Hence, speaking of "solutions" is a bit off.

The duality is between tessalations and triangulations: To move from the triangulation to the tesselation, you form the Voronoi set of the vertices of the triangulation. To move from the Voronoi tesselation to the Delaunay triangulation, you connect the "midpoints" of two cells if they touch each other.

$\endgroup$
1
$\begingroup$

Voronoi and Delaunay graphs are called dual for their graph properties. See Dual Graph on Wikipedia.

$\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.