Constructing a graph from points with edges determined by a Euclidean distance cutoff

Question

I have a collection of points in R^3 with a Euclidean distance metric. I would like to construct a graph with each point represented by a node, and edges only between points with distance d < r, where r is some cutoff value.

Searching stackoverflow yielded an interesting solution: to compute the Delaunay triangulation of the data points, and then to remove edges longer than the threshold distance.

(source: 3D Connected Points Labeling based on Euclidean distances)

Are there other ways to do this that are more efficient?

Also, what is an efficient way of removing edges longer than the cutoff distance?

If not, does anyone know of a Delaunay triangulation implementation in Python?

edit: nevermind the last question, matplotlib can do the triangulation, scipy for 3d.

Thanks.

PS - somewhat related: since the Delaunay triangulation is the dual graph of the Voronoi diagram, and k-means clustering splits space into Voronoi cells, is the method described here the same (or closely related to) k-means clustering? I'm a beginner in machine learning algorithms so I would love some expert feedback on this.

Answer 1

Your result may be the complete graph, so a Delaunay triangulation won't help. But you can use a kD-Tree.

http://en.wikipedia.org/wiki/K-d_tree