Why do the delaunay edges from Matlab's delaunayn() connect points with non-adjacent Voronoi regions?

Question

I am trying to find the points with edge-adjacent Voronoi regions in a given dataset. I'm new to computational geometry, but from reading up online, it appeared that using the Delaunay tessellation would be an easy way to do this. This PDF in particular even has a lemma that states

Lemma 2.4 Two points of S are joined by a Delaunay edge iff their Voronoi regions are edge-adjacent.

So, I found the delaunay tessellation of my dataset as

dt = delaunay(dataset); %using delaunayn() since dataset can be multidimensional

But now, when I plot this along with the voronoi diagram for this dataset, I find that the delaunay edges returned connect points whose regions are not actually edge-adjacent.

Here is the code I used to plot Voronoi and Delaunay together:

voronoi(dataset(:, 1),dataset(:, 2));
hold on;

dt = delaunayn(dataset);
triplot(dt, dataset(:, 1), dataset(:, 2), 'red');

And here is the output: Voronoi Delaunay plot

As an example of the problem, see the point X on the right end of the figure connected to point Y near the lower left corner.

Another example is in this SO question - the point 1 is connected to 2 and 3, even though they're not adjacent, and there doesn't seem to be any way 1 and 2 could share an edge even if extended to infinity. This question is actually what prompted me to test the delaunayn output with the above code.

Why is this happening, and how do I actually get the edge-adjacent neighbour regions that I need?

Note: For seeing the image in full size and clarity, please right click and choose 'View image' or similar.

Thanks for the hint for viewing the image in full size, didn't know that it was scaled down like that (bad filtering by the way, at least in Firefox). — Andre

Andre Andre · Accepted Answer · 2011-11-24T07:23:02

As far as I can see (the quality of the diagram is not so good), the regions for X and Y should be adjacent below the plotted part. If you zoom out far enough, you should see them.

I.e. the edge where X and Y meet exists, but is just not shown on the plot.

The following diagram does not show the voronoi diagram outside of the plotting area, but how to find the intersection point described above (note, the bisector is not shown here): extended voronoi diagram

Why do the delaunay edges from Matlab's delaunayn() connect points with non-adjacent Voronoi regions?

1 Answers