1

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.

Community
  • 1
  • 1
Sundar R
  • 13,776
  • 6
  • 49
  • 76
  • 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 Nov 24 '11 at 07:49

1 Answers1

2

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

Andre
  • 1,577
  • 1
  • 13
  • 25
  • If you have a look at the horizontal axis, there are four intersections with edges of the Voronoi graph. I'm pretty confident that the outer ones (at about 37 and 82) will intersect far down the cartesian plane. The intersection point will lie on the perpendicular bisector of X and Y, the same is true for the diagram in the linked question (although it lies to the right). Have you zoomed out of the graph? – Andre Nov 24 '11 at 07:51
  • Thanks a lot Andre. I first thought there was no way regions 1 and 2 in the linked question shared an edge, but I analyzed the image with Matlab's image processing toolbox, and found their slopes meant they do intersect! I guess that question itself was, strictly speaking, wrong in its assumptions. This is a heavy load off, thanks again. – Sundar R Nov 25 '11 at 07:28