[R] Delaunay Graph, once again

Raphael Päbst raphael.paebst at gmail.com
Fri Jun 20 17:17:12 CEST 2014

Hello again,
After playing around with my current problem for some time, I have
once again returned to Delaunay Graphs and after banging my head
against the problem for some time I fear that I can't see the issue
clearly anymore and want to ask for some outside comments, to maybe
shake my thoughts loose again.

So, let me explain my project and then my problem:
 I have a set of points, given as x- and y-coordinates and want to
create the adjacency matrix of the corresponding Delaunay Graph. I
have already removed duplicates in my set of points and to calculate
the matrix, I have hit upon the following procedure, which might not
be the most efficient, but I'm aiming for correct results and
simplicty first, before I can think about efficiency.

# x a vector of length n, containing the x-coordinates of my n points
#y: the same for the y-coordinates
del <- deldir(x, y) # calculating the tesselation
dels <- del$delsgs[,5:6] # giving me a data.frame with 2 columns,
containing the indices of points connected by an edge in the Delaunay

adj <- matrix(0, length(x), length(y)) # creating the empty adjacency matrix

for (i in 1:nrow(dels)){ # going through the rows of dels
adj[dels[i,1], dels[i,2]] <- 1; # since the points in a row of dels
are connected, the matrix at that point is set to 1
adj[dels[i,2], dels[i,1]] <- 1; # and this makes it symmetric

Now as I see it this should give me the adjacency matrix, right?

So let's come to my problem: The program I'm writing is a translation
of some Matlab-Code and so the results of both versions should be the
same, if at all possible. My adjacency matrix created in the above
mentioned manner however is not the same as the one created with
Matlab. The Matlab-Version uses algorithms based on Qhull, while I use
deldir as a library, could this account for the difference or have I
fundamentally misunderstood some part of the whole plan?

I hope the information is helpful and would very much appreciate any
pointers and thoughts on the matter.

Many thanks and all the best!


More information about the R-help mailing list