Search code examples
rdelaunayvoronoitessellation

Voronoi diagrams based on non metric distances in R

I want to voronoi diagrams in R. I have a set of points in N-dimensions(say 10). I dont want to use multi dimensional scaling(MDS). I want voronoi diagrams to be plotted using non metric measures. Is there any package which has this implementation? If not, then can you suggest me a suitable way to plot the tessellations using these N-dimensional co-ordinates.

Solution

  • It is not clear whether your problem is the dimension reduction or plotting the tessellation: the problems are separate. As suggested in the comments, you can use 

    library(sos)
???"non-metric"
???"Voronoi"

    to find where the functions you need are.

    # Sample data: a distance matrix
d <- dist( matrix( rnorm(200), nc=10 ) )

# Dimension reduction, via non-metric multidimensional scaling
library(MASS)
r <- sammon( d )

# Plot the Voronoi tessellation
library(tripack)
x <- r$points
plot( voronoi.mosaic(x[,1], x[,2]) )
points(x, pch=13)

    Besides principal component analysis (prcomp) and multidimensional scaling (MASS::isoMDS, MASS:sammon), you can also look at isomap (vegan::isomap), local linear embedding (lle::lle), maximum variance unfolding or T-distributed stochastic neighbor embedding (tsne::tsne): since some of those (Isomap, LLE, MVU) are based on the "neighbourhood graph", which is not unlike the 2-dimensional tessellation you seek, they may be more meaningful for your problem.